Coloring, sparseness and girth

Noga Alon, Alexandr Kostochka, Benjamin Reiniger, Douglas B. West, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


An r-augmented tree is a rooted tree plus r edges added from each leaf to ancestors. For d, g, r ∈ N, 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.

Original languageEnglish (US)
Pages (from-to)315-331
Number of pages17
JournalIsrael Journal of Mathematics
Issue number1
StatePublished - Jul 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Coloring, sparseness and girth'. Together they form a unique fingerprint.

Cite this