A Brooks-type result for sparse critical graphs

DOI10.1007/s00493-017-3068-3zbMath1424.05090arXiv1408.0846OpenAlexW2962855779MaRDI QIDQ1786052

Alexandr V. Kostochka, Matthew P. Yancey

Publication date: 24 September 2018

Published in: Combinatorica, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringimproper coloring\(k\)-critical graphssparse critical graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Further extensions of the Grötzsch theorem ⋮ On the minimum edge-density of 5-critical triangle-free graphs ⋮ The small stellated dodecahedron code and friends ⋮ On the minimum number of edges in triangle-free 5-critical graphs ⋮ Critical graphs for the chromatic edge-stability number ⋮ Structure in sparse \(k\)-critical graphs ⋮ A density bound for triangle‐free 4‐critical graphs ⋮ On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs ⋮ Sparse Graphs Are Near-Bipartite ⋮ Hajós-Type Constructions and Neighborhood Complexes ⋮ Characterizing 4-critical graphs with Ore-degree at most seven ⋮ Planar 4-critical graphs with four triangles ⋮ On 3-flow-critical graphs ⋮ Adynamic coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• On the edge-density of 4-critical graphs
• Planar 4-critical graphs with four triangles
• On the minimal number of edges in color-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Colorings of plane graphs: a survey
• Defective 2-colorings of sparse graphs
• Short proofs of coloring theorems on planar graphs
• Colour-critical graphs and hypergraphs
• Note on the colouring of graphs
• Map Colour Theorems Related To the Heawood Colour Formula
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Some Theorems on Abstract Graphs
• The structure of k-chromatic graphs
• 25 pretty graph colouring problems