Vertex colouring edge partitions
Vertex colouring edge partitions
复制标题
DOI：
10.1016/j.jctb.2005.01.001
复制
发表时间：
2005-07
期刊：
影响因子：
--
通讯作者：
L. Addario-Berry;R. Aldred;Ketan Dalal;B. Reed
中科院分区：
文献类型：
--
作者：
L. Addario-Berry;R. Aldred;Ketan Dalal;B. Reed
将图G的边划分为集合{S1，…，Sk}，为每个顶点v定义了一个多集v，其中x中的i的多重性等于Si中v的边数。我们证明了每个图的边都可以被划分成4个集合，使得所得到的多集合给出G的顶点着色。换句话说，对于G的每条边（u,v）， Xu≠Xv。进一步，如果G的最小度至少为1000，则E(G)被划分为3个集合，使得相应的多集合产生顶点着色。
A partition of the edges of a graph G into sets {S1,…,Sk} defines a multiset Xvfor each vertex v where the multiplicity of i in Xvis the number of edges incident to v in Si. We show that the edges of every graph can be partitioned into 4 sets such that the resultant multisets give a vertex colouring of G. In other words, for every edge (u,v) of G, Xu≠Xv. Furthermore, if G has minimum degree at least 1000, then there is a partition of E(G) into 3 sets such that the corresponding multisets yield a vertex colouring.