Double-Critical Graph Conjecture

A connected graph $G$ is double-critical if $\chi(G)=t$ and

\chi\bigl(G\setminus\{x,y\}\bigr)=t-2

for every edge $xy\in E(G)$ . Double-Critical Graph Conjecture. For every integer $t\geq3$ , the only double-critical $t$ -chromatic graph is the complete graph $K_t$ . This is the $s=2$ case of the Erdős–Lovász Tihany Conjecture and is stated as an open problem; its classification remains unresolved in general.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Double-critical graph conjecture
Let $G$ be a graph such that removing every edge reduces its chromatic number by two. Double-critical graph conjecture. Then $G$ is a complete graph. This is the $s=2$ case of the Erdős–Lovász–Tihany conjecture. It has been proved for claw-free graphs of chromatic number at most eight, but remains open in general.
source: Sean Longbrake and Juvaria Tariq, “Some Cases of the Erdős-Lovász Tihany Conjecture for Claw-free Graphs”, arXiv:2406.15164 (2024).

Sources & referencesView supporting material

Primary source

Yue Wang and Gexin Yu, “Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs”, arXiv:2008.08015 (2022).

Additional references

2 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1805.11437.

critical-graphs graph-coloring

1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Equivalent formulations 1