TY - JOUR
T1 - Coloring, sparseness and girth
AU - Alon, Noga
AU - Kostochka, Alexandr
AU - Reiniger, Benjamin
AU - West, Douglas B.
AU - Zhu, Xuding
N1 - Publisher Copyright:
© 2016, Hebrew University of Jerusalem.
PY - 2016/7/1
Y1 - 2016/7/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84983652662&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84983652662&partnerID=8YFLogxK
U2 - 10.1007/s11856-016-1361-2
DO - 10.1007/s11856-016-1361-2
M3 - Article
AN - SCOPUS:84983652662
SN - 0021-2172
VL - 214
SP - 315
EP - 331
JO - Israel Journal of Mathematics
JF - Israel Journal of Mathematics
IS - 1
ER -