2014/12/26 by Noga Alon, Alexandr Kostochka, Alon, Noga +7 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1412.8002
Slight adjustments, including simplifying the proofs of Lemmas 2.2 and 2.3 and the arguments for large girth
arxiv created 2015/04/30 · arxiv updated 2015/05/01
An r-augmented tree is a rooted tree plus r edges added from each leaf to ancestors. For d,g,r∈ℕ, we construct 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 the girth. Using the resulting graphs, we construct 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. We also give a new simple construction of non-k-colorable graphs and hypergraphs with any girth g.