A Brooks-type result for sparse critical graphs
From MaRDI portal
Publication:1786052
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
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