Double-critical graph conjecture

Medium ★★ Graph Theory » Coloring » Vertex coloring

Authors: Erdos, Paul, Lovasz, Laszlo— posted by DFR on 2009-01-18

Status partial high confidence

The conjecture that $K_n$ is the only $n$-chromatic double-critical graph remains open for $n \geq 6$ in general. Substantial partial progress has been made since the OPG posting: the conjecture is now verified for claw-free graphs with chromatic number $t \leq 8$, and every double-critical $t$-chromatic graph is known to contain a $K_t$ minor for all $t \leq 9$.

Cited literature (5)

partial Double-Critical Graphs and Complete Minors (2010)

Ken-ichi Kawarabayashi, Anders Sune Pedersen, Bjarne Toft · Electronic Journal of Combinatorics · arXiv:0810.3133 · doi:10.37236/359

Proves that for $k=6$ and $k=7$, any non-complete double-critical $k$-chromatic graph is 6-connected and contains $K_k$ as a minor.
partial Complete and almost complete minors in double-critical 8-chromatic graphs (2010)

Anders Sune Pedersen · arXiv preprint · arXiv:1007.5400

Proves every double-critical 8-chromatic graph contains a $K_8^-$ minor, and a full $K_8$ minor when the minimum degree is not 10 or 11.
partial A note on the double-critical graph conjecture (2016)

Hao Huang, Alexander Yu · arXiv preprint · arXiv:1604.05262

Proves the conjecture for claw-free double-critical graphs of chromatic number 6.
partial Clique Minors in Double-critical Graphs (2016)

Martin Rolek, Zi-Xia Song · arXiv preprint · arXiv:1603.06964

Proves every double-critical $t$-chromatic graph contains a $K_t$ minor for all $t \leq 9$.
partial Double-critical graph conjecture for claw-free graphs (2016)

Martin Rolek, Zi-Xia Song · Discrete Mathematics · arXiv:1610.00636

Proves the Erdős–Lovász conjecture for claw-free double-critical graphs of chromatic number $t \leq 8$.

Reviewer notes. A ResearchGate page (publication ID 362648627) titled 'On the double-critical graph conjecture' was inaccessible (HTTP 403); a search snippet suggested it might contain a complete proof via a universal-vertex argument, but this could not be verified and the paper is not cited. The arXiv preprint 0810.3133 was submitted in October 2008 (before the OPG posting date) but published in EJC in June 2010; it is included with year 2010. arXiv:1603.06964 was verified as submitted in 2016 but revised in 2017; year listed as 2016. The ScienceDirect page for arXiv:1610.00636 (Discrete Math., 2017) was not fetched; the arXiv URL is used instead.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 06) (web search enabled).

Conjecture. $ K_n $ is the only $ n $ -chromatic double-critical graph

Keywords: coloring · complete graph

Discussion

This conjecture is a special case of a more general problem by Erdos and Lovasz proposed in 1966. It has been independently proven for the case where $ \chi(G) = 5 $ by Mozhan [3] and Stiebitz [4].

Bibliography

★ [1] P. Erdos, Problem 2, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, p. 361.
[2] F. Chung, R. Graham, Erdos on graphs: His legacy of unsolved problems, A K Peters, Wellesley, Massachusetts, 1998.
[3] N. N. Mozhan, On double critical graphs with the chromatic number five, Metody Diskretb. Anal. 46 (1987) 50-59.
[4] M. Stiebitz, $ K_5 $ is the only double-critical $ 5 $ -chromatic graph, Discrete Math. 64 (1987) 91-93.