Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture |
| |
Authors: | Henry A Kierstead Alexandr V Kostochka |
| |
Institution: | 1. School of Mathematical and Statistical Sciences, Arizona State University, P.O. Box 871804, Tempe, AZ, 85287, USA 2. Department of Mathematics, University of Illinois, 1409 W. Green St., Urbana, IL, 61801, USA 3. Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia
|
| |
Abstract: | Chen, Lih, 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-Szemerédi 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
and V(G) partitions into subsets V
0, …, V
t
such that GV
0] = K
r,r
and for each 1 ≤ i ≤ t, GV
i
] = 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|