Abstract
A proper vertex coloring of a graph is equitable if the sizes of its color classes differ by at most one. In this paper, we prove that if G is a graph such that for each edge x y ∈ E (G), the sum d (x) + d (y) of the degrees of its ends is at most 2 r + 1, then G has an equitable coloring with r + 1 colors. This extends the Hajnal-Szemerédi Theorem on graphs with maximum degree r and a recent conjecture by Kostochka and Yu. We also pose an Ore-type version of the Chen-Lih-Wu Conjecture and prove a very partial case of it.
Original language | English (US) |
---|---|
Pages (from-to) | 226-234 |
Number of pages | 9 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 98 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2008 |
Keywords
- Equitable coloring
- Ore-type
- Packing
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics