Coloring, sparseness and girth

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

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume214
Issue number1
DOIs
StatePublished - Jul 1 2016

ASJC Scopus subject areas

  • Mathematics(all)

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

Cite this