The total colouring conjecture

Every graph satisfies \(\chi''(G) \le \Delta(G) + 2\): vertices and edges together need at most two more colours than the maximum degree.

Behzad (1965) and Vizing (1968) asked whether colouring vertices and edges together ever costs more than two extra colours beyond the maximum degree. The fractional version fell (Kilpatrick 1975, Reed); Molloy–Reed (1998) bounded the gap by a constant (\(\Delta + 10^{26}\) famously, later improved); the exact \(\Delta+2\) stands open even for highly structured classes, though it holds for complete graphs, bipartite graphs, and all graphs with \(\Delta \ge\) something large only in weakened forms. A rare conjecture that is simultaneously elementary to state and untouched at its core.