Papex

Open problem · Mathematics · Open

Total colouring conjecture

Can the vertices and edges of every graph be coloured with at most Δ + 2 colours, Δ being the maximum degree, so that no adjacent or incident elements match?

Summary

Mehdi Behzad and Vadim Vizing introduced the conjecture independently between 1964 and 1968. At least Δ + 1 colours are always needed, and the conjecture is known for several classes of graphs, including all bipartite graphs; in 1998 Molloy and Reed showed that Δ plus a very large fixed constant always suffices.

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics