On equitable -coloring of graphs with low average degree
On equitable -coloring of graphs with low average degree
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. V. Kostochkaa;K. Nakprasita
中科院分区：
文献类型：
--
作者：
A. V. Kostochkaa;K. Nakprasita
图的均匀染色是指图的任意两个色类的大小相差不超过1的正常顶点染色。Hajnal和Szemerédi证明了每个具有最大度的图对每个k + 1都是公平k-可着色的。Chen，Lih和Wu证明了每个最大度为3且不同于K +1和K的连通图都是均匀可着色的.这一猜想已在一些图类如二部图、外平面图、最大度为3的图、区间图中得到了证明。我们证明了这个猜想对平均度至多为/5的图成立。© 2005爱思唯尔有限公司版权所有。
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. Hajnal and Szemerédi proved that every graph with maximum degree is equitably k-colorable for every k + 1. Chen, Lih, and Wu conjectured that every connected graph with maximum degree 3 distinct from K +1 and K , is equitably -colorable. This conjecture has been proved for graphs in some classes such as bipartite graphs, outerplanar graphs, graphs with maximum degree 3, interval graphs. We prove that this conjecture holds for graphs with average degree at most /5. © 2005 Elsevier B.V. All rights reserved.