Ore's conjecture for \(k=4\) and Grötzsch's theorem

zbMath1349.05111arXiv1209.1173MaRDI QIDQ397076

Matthew P. Yancey, Alexandr V. Kostochka

Publication date: 14 August 2014

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

coloring\(k\)-ciritical graphGrötsch's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items

Further extensions of the Grötzsch theorem ⋮ I,F-partitions of sparse graphs ⋮ Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains ⋮ On the minimum number of edges in triangle-free 5-critical graphs ⋮ The minimum number of edges in 4-critical digraphs of given order ⋮ A density bound for triangle‐free 4‐critical graphs ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ Homomorphisms to small negative even cycles ⋮ Density of 5/2-critical graphs ⋮ Unnamed Item ⋮ Short proofs of coloring theorems on planar graphs ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ An introduction to the discharging method via graph coloring ⋮ Characterizing 4-critical graphs with Ore-degree at most seven ⋮ The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges ⋮ A Brooks-type result for sparse critical graphs ⋮ Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs ⋮ Counting critical subgraphs in \(k\)-critical graphs ⋮ Density of \(C_{-4}\)-critical signed graphs