Nov. 12, 3:30pm, Wean 8220

Sasha Kostochka, UIUC

Colorings and list colorings of sparse graphs

Sasha Kostochka, UIUC

Colorings and list colorings of sparse graphs

Abstract:

The goal of the talk is to present two closely related results.
The first (joint with Reiniger) is a proof of a conjecture by Chen,
Erdős, Gyárfás and Schelp on the number of edges in *4*-critical graphs that become bipartite after
deleting *3* edges.
A useful part of the proof is the result of Alon and Tarsi that every
bipartite graph with maximum
average degree at most *4* is *3*-list-colorable. It would be helpful if
every such bipartite graph
after adding one more edge was still *3*-list-colorable. But this turned out
to be not the case.
The second result (joint with Alon, Reiniger, West and Zhu) is a
construction for every *k* and *g* of a bipartite graph of girth at least *g* that after deleting
any edge has maximum average degree at most *2*(*k*-*1*) but is not *k*-list-colorable. As a
biproduct, we get a new construction of graphs and hypergraphs with arbitrarily high girth and
chromatic number.