Equitable Coloring of Graphs and Digraphs

Graphs, Hypergraphs, and Computing

04 March 14:00 - 15:00

Hal Kierstead - Arizona State University

In 1963, Corrádi and Hajnal proved that for all positive integers k and n \ge 3k, every graph G on n vertices with \delta(G) \ge 2k contains k disjoint cycles. When n = 3k, this says that G can be partitioned into k triangles, and in complementary form, that if \Delta(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 \Delta(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 \chi(G) \le \Delta(G), unless G contains a (\Delta(G)+1)-clique or both \Delta(G) = 2 and G contains an odd cycle. The major open question in this area is to characterize those graphs G with \chi(G) \le \Delta(G) that have an equitable \Delta(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 \delta(G) \ge 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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to