Ore's conjecture on color-critical graphs is almost true
From MaRDI portal
Publication:462926
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
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