Hal Kierstead: Equitable Coloring of Graphs and Digraphs

In 1963, Corrádi and Hajnal proved that for all positive integers k and n ≥ 3k, every graph G on n vertices with  Δ(G) ≥ 2k contains k disjoint cycles. When n = 3k, this says that G can be partitioned into k triangles, and in complementary form, that if Δ(G) < k then G has a k-coloring such that every color class has size three. In 1970, Hajnal and Szemerédi extended this special case of the Corrádi-Hajnal Theorem by proving that every graph G with Δ(G) < k has an equitable k-coloring, i.e., G can be k-colored so that any two color classes differ in size by at most one.

The degree bounds of these theorems are sharp---if we relax them then there are counterexamples. However, it still makes sense to try to characterize all counterexamples. For example, Brooks' Theorem states that χ(G) ≤ Δ(G), unless G contains a (Δ(G)+1)-clique or both Δ(G) = 2 and G contains an odd cycle. The major open question in this area is to characterize those graphs G with χ(G) ≤ Δ(G) that have an equitable Δ(G)-coloring. One counterexample is K_{t,t} when t is odd.

I will report on recent results concerning these and related questions, including:

1. A characterization of those graphs with δ(G) ≥ 2k-1 that contain k disjoint cycles.
2. Directed versions of the Hajnal-Szemeredi Theorem.

The talk is based on work with Czygrinow, DeBiasio, Kostochka, Molla, Mydlarz, Szemerédi, and Yeager.