Coloring, Sparseness and Girth

An \(r\)-augmented tree is a rooted tree plus \(r\) edges added from each leaf to ancestors. For \(d, g, r\in\mathbb{N}\), the speaker constructs a bipartite \(r\)-augmented complete \(d\)-ary tree having girth at least \(g\). The height of such trees must grow extremely rapidly in terms of girth.

Using the resulting graphs, the speaker constructs sparse non-\(k\)-choosable bipartite graphs, showing that maximum average degree at most \(2(k-1)\) is a sharp sufficient condition for \(k\)-choosability in bipartite graphs, even when requiring large girth. The speaker also gives a new simple construction of non-\(k\)-colorable graphs and hypergraphs with any girth \(g\).

This is joint work with Alon, Kostochka, West, and Zhu.

Event Topic

Discrete Applied Math Seminar