Seminar

# Equitable Coloring of Graphs and Digraphs

#### 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.
Organizers
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski