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

zbMATH Open1349.05111arXiv1209.1173MaRDI QIDQ397076FDOQ397076

Authors: Matthew Yancey, Alexandr Kostochka 

Publication date: 14 August 2014

Published in: Combinatorica (Search for Journal in Brave)

Abstract: A graph $G$ is $k$-{em 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. In a very recent paper, we gave a lower bound, $f_k(n)geqF(k,n)$, that is sharp for every $n=1,(mmod,k-1)$. It is also sharp for $k=4$ and every $ngeq6$. In this note, we present a simple proof of the bound for $k=4$. It implies the case $k=4$ of 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)$. We also show that our result implies a simple short proof of the Gr" otzsch Theorem that every triangle-free planar graph is 3-colorable.

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

Recommendations

• Ore's conjecture on color-critical graphs is almost true
• Short proofs of coloring theorems on planar graphs
• Characterizing 4-critical graphs with Ore-degree at most seven
• Colour-critical graphs with few edges
• On the edge-density of 4-critical graphs

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)

Cited In (31)

• Characterizing 4-critical graphs with Ore-degree at most seven
• On the minimum number of arcs in \(k\)-dicritical oriented graphs
• A proof of Tomescu's graph coloring conjecture
• Further extensions of the Grötzsch theorem
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Density of 5/2-critical graphs
• Three-coloring triangle-free graphs on surfaces. II: 4-critical graphs in a disk
• The Prasad conjectures for \(\mathrm{GSp}_4\) and \(\mathrm{PGSp}_4\)
• Density of 3-critical signed graphs
• Three coloring via triangle counting
• I,F-partitions of sparse graphs
• Ore's conjecture on color-critical graphs is almost true
• Planar 4-critical graphs with four triangles
• The minimum number of edges in 4-critical digraphs of given order
• Density of \(C_{-4}\)-critical signed graphs
• Three-coloring triangle-free graphs on surfaces. IV: Bounding face sizes of 4-critical graphs
• Title not available (Why is that?)
• Note to a problem of T. Gallai and G. A. Dirac
• On the minimum number of edges in triangle-free 5-critical graphs
• Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
• A density bound for triangle‐free 4‐critical graphs
• Homomorphisms to small negative even cycles
• The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges
• On the density of \(C_7\)-critical graphs
• Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains
• Counting critical subgraphs in \(k\)-critical graphs
• An introduction to the discharging method via graph coloring
• 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
• Short proofs of coloring theorems on planar graphs
• Title not available (Why is that?)

This page was built for publication: Ore's conjecture for \(k=4\) and Grötzsch's theorem

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