Total coloring conjecture

Color both the dots and links of a network. Joined dots must differ; links meeting at a dot must differ; a link must differ from either endpoint. Even two dots joined by one link need three colors. Can every finite simple undirected graph obey all three rules using at most two more colors than its maximum degree, the largest number of links touching any dot?[1] [2]

Can the two kinds of local coloring conflict be satisfied with almost the smallest palette forced at a single junction? On a triangle, color vertices A, B, C red, blue, green, then color AB green, BC red, CA blue. This satisfies every rule using three colors.

For a finite simple undirected graph $G$, a total coloring colors both $V(G)$ and $E(G)$, distinguishing adjacent vertices, adjacent edges and incident vertex–edge pairs. Write $\chi^{\prime\prime}(G)$ for its minimum number of colors and $\Delta(G)$ for the maximum degree. A vertex of degree $\Delta(G)$ and its incident edges force at least $\Delta(G)+1$ colors. Is $\chi^{\prime\prime}(G)\leq\Delta(G)+2$ always true?[2]

The published large-degree work proves bounds and a result for sufficiently large dense regular graphs. A 2026 preprint treats selected planar graphs with maximum degree six. Those conditions leave the general graph question uncovered.[1] [2]

The 2025 published paper confirms the conjecture for sufficiently large regular graphs whose degree exceeds half their order by a fixed positive proportion. The planar degree-six preprint adds restrictions on four-cycles. Neither removes the hypotheses for arbitrary simple graphs. The listed published discussion also describes an earlier universal proof announcement as unverified.[1] [2] [3]

A busy junction forces its dot and all its links to use different colors. Farther away, the same colors may be reused, but the requirements for dots and links must remain compatible. This is a question about combining two local kinds of conflict into one global assignment, instead of giving each kind a separate palette.[1] [2]

At a highest-degree vertex the conflicts form one tightly coupled group, giving the local lower bound. A separate vertex coloring and edge coloring can always avoid each other by using disjoint palettes, but that construction loses all opportunities for shared colors. The conjecture asks how global structure permits those opportunities without violating either kind of conflict. The triangle example shows the same three colors doing different jobs at different places.[2]