Total Colouring 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.

For a finite simple graph $G$, a proper total coloring assigns colors to $V(G)\cup E(G)$ so that adjacent vertices, edges sharing a vertex, and incident vertex--edge pairs have different colors. Let $\chi''(G)$ be the minimum number of colors and $\Delta(G)$ the maximum degree.

Statement recorded in the supplied source.

Does every graph $G$ satisfy \[\chi''(G)\in\{\Delta(G)+1,\Delta(G)+2\},\] equivalently $\chi''(G)\le\Delta(G)+2$? [S2]

Short English statement

Are at most two more colors than the maximum degree enough to color vertices and edges simultaneously?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3192 (OPG-815). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Total Colouring Conjecture, original node 815, statement and mathematical discussion. https://www.openproblemgarden.org/op/behzads_conjecture.