## 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 G[V_{0}] = K_{r,r} and for each 1 ≤ i ≤ t, G[V_{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.

Original language | English (US) |
---|---|

Pages (from-to) | 201-216 |

Number of pages | 16 |

Journal | Combinatorica |

Volume | 30 |

Issue number | 2 |

DOIs | |

State | Published - Sep 24 2010 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Computational Mathematics