EQUITABLE COLORING OF 2-DEGENERATE GRAPH AND PLANE GRAPHS WITHOUT CYCLES OF SPECIFIC LENGTHS
Yuehua Bu, Qiong Li, SHUIMING ZHANG · Discrete Mathematics Algorithms and Applications · 2010
The equitable chromatic number χe(G) of a graph G is the smallest integer k for which G has a proper k-coloring such that the number of vertices in any two color classes differ by at most one. In 1973, Meyer conjectured that the equitable chromatic number of a connected graph G, which is neither a complete graph nor an odd cycle, is at most Δ(G). We prove that this conjecture holds for 2-degenerate graphs with Δ(G) ≥ 5 and plane graphs without 3, 4 and 5 cycles.