Seminar

# 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.

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

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU