Double-critical graph conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite connected simple graph $G$ is double-critical if $\chi(G-\{u,v\})=\chi(G)-2$ for every edge $uv$. Here vertex deletion removes all incident edges, and $\chi$ is the proper vertex chromatic number. Let $K_n$ denote the complete graph on $n$ vertices.

Statement recorded in the supplied source.

For every integer $n\ge2$, is every $n$-chromatic double-critical graph isomorphic to $K_n$? [S2]

Short English statement

Are complete graphs the only connected graphs whose chromatic number drops by two after deleting any adjacent pair?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3236 (OPG-34839). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Double-critical graph conjecture, original node 34839, statement and mathematical discussion. https://www.openproblemgarden.org/op/double_critical_graph_conjecture.