EQUITABLE VERSUS NEARLY EQUITABLE COLORING AND THE CHEN-LIH-WU CONJECTURE

作者：Kierstead Henry A^*; Kostochka Alexandr V

来源：Combinatorica, 2010, 30(2): 201-216.

DOI：10.1007/s00493-010-2420-7

Chen, Lila, and Wu conjectured that for r >= 3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are K(r,r) (for odd r) and K(r+1). If true, this would be a strengthening of the Hajnal-Szerneredi Theorem and Brooks' Theorem. We extend their conjecture to disconnected graphs. For r >= 6 the conjecture says the following: If an r-colorable graph G with maximum degree r is not equitably r-colorable then r is odd, G contains K(r,r) arid V(G) partitions into subsets V(o), ... ,V(t) such that G[V(0)] = K(r,r) and for each 1 <= i <= t, G[Vi] = K(r.) We characterize graphs satisfying the conclusion of our conjecture for all r and use the characterization to prove that the two conjectures are equivalent. This new conjecture may help to prove the Chen Lih Wu Conjecture by induction.

• 出版日期2010