zbMATH — the first resource for mathematics

Coloring, sparseness and girth. (English) Zbl 1344.05058
Summary: An \(r\)-augmented tree is a rooted tree plus \(r\) edges added from each leaf to ancestors. For \(d,g,r \in \mathbb 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.

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
05C65 Hypergraphs
Full Text: DOI arXiv
[1] Alon, N., Combinatorial nullstellensatz, combinatorics, Probability and Computing, 8, 7-29, (1999) · Zbl 0920.05026
[2] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[3] Erdos, P., Graph theory and probability, Canadian Journal of Mathematics, 11, 34-38, (1959) · Zbl 0084.39602
[4] Erdos, P.; Hajnal, A., On chromatic number of graphs and set-systems, Acta Mathematica Academiae Scientiarum Hungaricae, 17, 61-99, (1966) · Zbl 0151.33701
[5] Erdos, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, in Proceedings of the west coast conference onn combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, CA., 1979), Congressus Numerantium, 26, 125-157, (1980)
[6] Füredi, Z.; Kostochka, A.; Kumbhat, M., Choosability with separation of complete multipartite graphs and hypergraphs, Journal of Graph Theory, 76, 129-137, (2014) · Zbl 1291.05063
[7] Hakimi, S. L., On the degrees of the vertices of a directed graph, Journal of the Franklin Institute, 279, 290-308, (1965) · Zbl 0173.26404
[8] Kostochka, A. V.; Nesetril, J., Properties of descartes’ construction of trianglefree graphs with high chromatic number, combinatorics, Probability and Computing, 8, 467-472, (1999) · Zbl 0951.05036
[9] Kostochka, A. V.; Stiebitz, M., On the number of edges in colour-critical graphs and hypergraphs, Combinatorica, 20, 521-530, (2000) · Zbl 0996.05046
[10] Kratochvíl, J.; Tuza, Zs.; Voigt, M., Brooks-type theorems for choosability with separation, Journal of Graph Theory, 27, 43-39, (1998) · Zbl 0894.05016
[11] Kriz, I., No article title, A hypergraph free construction of highly chromatic graphs without short cycles, 9, 227-229, (1989)
[12] Lovász, L., On chromatic number of finite set-systems, Acta Mathematica Academiae Scientiarum Hungaricae, 19, 59-67, (1968) · Zbl 0157.55203
[13] Nesetril, J.; Rödl, V., Chromatically optimal rigid graphs, Journal of Combinatorial Theory. B, 46, 133-141, (1989) · Zbl 0677.05031
[14] Richardson, M., Solutions of irreflexive relations, Annals of Mathematics, 58, 573-580, (1953) · Zbl 0053.02902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.