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

DOI10.1016/J.JCTB.2014.05.002zbMATH Open1301.05127arXiv1209.1050OpenAlexW2148392390MaRDI QIDQ462926FDOQ462926

Authors: Alexandr Kostochka, Matthew Yancey 

Publication date: 22 October 2014

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

Abstract: A graph $G$ is $k$-critical if it has chromatic number $k$, but every proper subgraph of $G$ is $(k-1)$--colorable. Let $f_k(n)$ denote the minimum number of edges in an $n$-vertex $k$-critical graph. We give a lower bound, $f_k(n)geqF(k,n)$, that is sharp for every $n=1(mmodk-1)$. It is also sharp for $k=4$ and every $ngeq6$. The result improves the classical bounds by Gallai and Dirac and subsequent bounds by Krivelevich and Kostochka and Stiebitz. It establishes the asymptotics of $f_k(n)$ for every fixed $k$. It also proves that the conjecture by Ore from 1967 that for every $kgeq4$ and $ngeqk+2$, $f_k(n+k-1)=f(n)+frack-12(k-frac2k-1)$ holds for each $kgeq4$ for all but at most $k^3/12$ values of $n$. We give a polynomial-time algorithm for $(k-1)$-coloring a graph $G$ that satisfies $|E(G[W])|<F_k(|W|)$ for all $WsubseteqV(G)$, $|W|geqk$. We also present some applications of the result.

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

Recommendations

• On color critical graphs
• Total coloring conjecture for certain classes of graphs
• scientific article; zbMATH DE number 3924804
• A conclusion on the properties of edge-coloring critical graphs
• scientific article; zbMATH DE number 4043873
• Two conjectures on uniquely totally colorable graphs
• A conjecture on edge coloring of graphs
• On the minimal number of edges in color-critical graphs
• On a conjecture about uniquely colorable perfect graphs
• On constructive methods in the theory of colour-critical graphs

zbMATH Keywords

graph coloringsparse graphs\(k\)-critical graphs

Mathematics Subject Classification ID

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

Cites Work

• Ore-type versions of Brooks' theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• 25 pretty graph colouring problems
• A short list color proof of Grötzsch's theorem
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• On the edge-density of 4-critical graphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• On the number of edges in colour-critical graphs and hypergraphs
• Graphs with chromatic number close to maximum degree
• Title not available (Why is that?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Note on the colouring of graphs
• Map Colour Theorems Related To the Heawood Colour Formula
• A new proof of Grünbaum's 3 color theorem
• Short proofs of coloring theorems on planar graphs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (41)

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

This page was built for publication: Ore's conjecture on color-critical graphs is almost true

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462926)