Coloring, sparseness and girth

DOI10.1007/S11856-016-1361-2zbMATH Open1344.05058arXiv1412.8002OpenAlexW1855957319WikidataQ106158897 ScholiaQ106158897MaRDI QIDQ312271FDOQ312271

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

Publication date: 15 September 2016

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1412.8002

zbMATH Keywords

\(r\)-augmented treenon-\(k\)-colorable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Cites Work

• Graph Theory and Probability
• On the degrees of the vertices of a directed graph
• Solutions of irreflexive relations
• Title not available (Why is that?)
• Combinatorial Nullstellensatz
• Chromatically optimal rigid graphs
• Colorings and orientations of graphs
• Brooks-type theorems for choosability with separation
• Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number
• Choosability with Separation of Complete Multipartite Graphs and Hypergraphs
• On chromatic number of graphs and set-systems
• On chromatic number of finite set-systems
• On the number of edges in colour-critical graphs and hypergraphs
• A hypergraph-free construction of highly chromatic graphs without short cycles

Cited In (12)

• Graphs with large girth and chromatic number are hard for Nullstellensatz
• High girth hypergraphs with unavoidable monochromatic or rainbow edges
• Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
• Generalized signed graphs of large girth and large chromatic number
• High girth augmented trees are huge
• List Coloring with a Bounded Palette
• Girth and λ $\lambda $‐choosability of graphs
• Graphs of large chromatic number
• Graphs vertex-partitionable into strong cliques
• Separation Choosability and Dense Bipartite Induced Subgraphs
• Circular chromatic number of signed graphs
• Girth, Pebbling, and Grid Thresholds

This page was built for publication: Coloring, sparseness and girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q312271)