The ACO Seminar (2015–2016)

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.