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.
- Equitable coloring
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics