Coloring, sparseness and girth

DOI10.1007/S11856-016-1361-2zbMath1344.05058arXiv1412.8002OpenAlexW1855957319WikidataQ106158897 ScholiaQ106158897MaRDI QIDQ312271

Benjamin Reiniger, Xuding Zhu, Noga Alon, Douglas B. West, Alexandr V. 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

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

Related Items (10)

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

Cites Work

• Unnamed Item
• A hypergraph-free construction of highly chromatic graphs without short cycles
• Chromatically optimal rigid graphs
• Colorings and orientations of graphs
• On the degrees of the vertices of a directed graph
• Solutions of irreflexive relations
• Graph Theory and Probability
• Combinatorial Nullstellensatz
• 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

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