Ore's conjecture on color-critical graphs is almost true

DOI10.1016/j.jctb.2014.05.002zbMath1301.05127arXiv1209.1050OpenAlexW2148392390MaRDI QIDQ462926

Matthew P. Yancey, Alexandr V. Kostochka

Publication date: 22 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringsparse graphs\(k\)-critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Related Items

I,F-partitions of sparse graphs ⋮ Point partition numbers: decomposable and indecomposable critical graphs ⋮ A better lower bound on average degree of 4-list-critical graphs ⋮ On the minimum edge-density of 5-critical triangle-free graphs ⋮ On the density of \(C_7\)-critical graphs ⋮ Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\) ⋮ On the minimum number of edges in triangle-free 5-critical graphs ⋮ The minimum number of edges in 4-critical digraphs of given order ⋮ Structure in sparse \(k\)-critical graphs ⋮ A density bound for triangle‐free 4‐critical graphs ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Generalized DP-colorings of graphs ⋮ On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ Some results on \(k\)-critical \(P_5\)-free graphs ⋮ Homomorphisms to small negative even cycles ⋮ Unnamed Item ⋮ Short proofs of coloring theorems on planar graphs ⋮ Sparse Graphs Are Near-Bipartite ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ Characterizing 4-critical graphs with Ore-degree at most seven ⋮ The edge density of critical digraphs ⋮ A better lower bound on average degree of online \(k\)-list-critical graphs ⋮ The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges ⋮ A Brooks-type result for sparse critical graphs ⋮ A local epsilon version of Reed's conjecture ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ On 3-flow-critical graphs ⋮ Density of \(C_{-4}\)-critical signed graphs ⋮ Large cliques and independent sets all over the place ⋮ Adynamic coloring of graphs ⋮ Tools for counting odd cycles in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Graphs with chromatic number close to maximum degree
• On the edge-density of 4-critical graphs
• Ore-type versions of Brooks' theorem
• On the minimal number of edges in color-critical graphs
• A new proof of Grünbaum's 3 color theorem
• A short list color proof of Grötzsch's theorem
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Short proofs of coloring theorems on planar graphs
• 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
• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Some Theorems on Abstract Graphs
• 25 pretty graph colouring problems
• On the number of edges in colour-critical graphs and hypergraphs