On equitable Delta-coloring of graphs with low average degree
On equitable Delta-coloring of graphs with low average degree
复制标题
DOI：
10.1016/j.tcs.2005.09.031
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
A. Kostochka;Kittikorn Nakprasit
中科院分区：
文献类型：
--
作者：
A. Kostochka;Kittikorn Nakprasit
图的均匀染色是指图的任意两个色类的大小相差不超过1的正常顶点染色。Hajnal和Szemerédi证明了每个最大度为Δ的图对于每个k <$Δ +1都是公平k-可着色的。Chen，Lih和Wu证明了：每个最大度Δ φ 3不同于KΔ +1和KΔ，Δ的连通图都是Δ-可染的.这一猜想已在一些图类如二部图、外平面图、最大度为3的图、区间图中得到了证明。我们证明了这个猜想对平均度不超过Δ/5的图成立。
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Δ+1and 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.