Coloring, sparseness and girth

DOI10.1007/S11856-016-1361-2MaRDI QIDQ312271zbMATH OpenOpenAlexWikidataFDO

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

Publication date 15 September 2016

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

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)

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$.

Recommendations

• Improper coloring of sparse graphs with a given girth. II: Constructions
• \((k,1)\)-coloring of sparse graphs
• scientific article; zbMATH DE number 1153458
• Sparse anti-Ramsey graphs
• Constructions of sparse uniform hypergraphs with high chromatic number

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• A hypergraph-free construction of highly chromatic graphs without short cycles
• Brooks-type theorems for choosability with separation
• Choosability with separation of complete multipartite graphs and hypergraphs
• Chromatically optimal rigid graphs
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Graph Theory and Probability
• On chromatic number of finite set-systems
• On chromatic number of graphs and set-systems
• On the degrees of the vertices of a directed graph
• On the number of edges in colour-critical graphs and hypergraphs
• Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number
• Solutions of irreflexive relations

Cited in

(12)

• Girth, Pebbling, and Grid Thresholds
• Graphs with large girth and chromatic number are hard for Nullstellensatz
• Separation choosability and dense bipartite induced subgraphs
• 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
• Circular chromatic number of signed graphs

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)