The Total Coloring Conjecture

The Total Colouring Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A total colouring assigns colours to both $V(G)$ and $E(G)$. Adjacent vertices, edges sharing a vertex, and an edge together with either endpoint must receive different colours. Write $\chi''(G)$ for the minimum number of colours and $\Delta(G)=\max_v\deg(v)$. The conjecture is $\chi''(G)\leq\Delta(G)+2$ for every finite simple graph. [S1] [S2]

Statement recorded in the supplied source.

Can every graph be totally colored with at most $\Delta + 2$ colors, where $\Delta$ is the maximum degree? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove the Delta+2 total-coloring bound for every graph. [S1]

Short English statement

Can the vertices and edges of every graph be coloured without any incidence conflicts using at most two more colours than its maximum degree?

Research attempt: constructive tree colourings and sharp complete-graph tests

Status and source scope. This is a partial attempt, not a proof of the general conjecture. The inspected abstract of [S2] concerns a restricted planar class. The elementary constructions below are proved here and make no novelty claim.

1. Reformulating the conflict constraints

Form the total graph $T(G)$, whose vertices are the objects $V(G)\sqcup E(G)$ and whose adjacency is exactly a forbidden equality of colours in the question. A vertex-object $v$ has degree $2d_G(v)$; an edge-object $uv$ has degree $d_G(u)+d_G(v)$. Consequently greedy colouring proves \[\Delta+1\leq\chi''(G)\leq2\Delta+1\] when $G$ has an edge: the lower bound is the clique consisting of a maximum-degree vertex and its incident edges. For $\Delta=1$, a component $K_2$ actually forms a triangle in the total graph and needs three colours. This exposes a boundary exception to any proposed universal $\Delta+1$ argument.

2. A complete construction for trees

Let $T$ be a tree with maximum degree $\Delta\geq2$, and use a fixed palette of $\Delta+1$ colours. Root the tree. Colour the root arbitrarily and colour its incident edges distinctly with the other colours. Suppose a non-root vertex $v$ is reached after its parent $u$ and the parent edge $uv$ have been coloured. Choose the colour of $v$ to avoid the two distinct colours on $u$ and $uv$; there are at least $\Delta-1\geq1$ choices. There are then $\Delta-1$ colours other than the colours of $v$ and $uv$. Assign distinct members of this set to the at most $\Delta-1$ child edges of $v$.

Continue by distance from the root. Every vertex differs from its parent; every edge differs from both endpoints once the child is coloured; and the edges incident at each vertex have distinct colours. There are no additional conflicts, because a tree has no edges between different branches. Thus \[\chi''(T)=\Delta+1\qquad(\Delta\geq2).\] The argument also handles forests componentwise, with isolated edges requiring three colours and isolated vertices requiring one. It is constructive and does not need an edge-colouring theorem.

3. Why the extra colour can be necessary

Let $n\geq2$ be even and consider $K_n$. A total colouring with $n$ colours would give its $n$ vertices all different colours, so every colour occurs on exactly one vertex. Edges of a fixed colour form a matching avoiding that vertex, and hence contain at most $(n-2)/2$ edges. Across all $n$ colours this accounts for at most $n(n-2)/2$ edges, fewer than the actual $n(n-1)/2$. Therefore $\chi''(K_n)\geq n+1=\Delta+2$.

For the reverse inequality put $q=n+1$, an odd integer, label $n$ vertices by distinct residues modulo $q$, colour vertex $i$ by $2i$, and colour edge $ij$ by $i+j$. Doubling is injective modulo odd $q$. At a fixed vertex $i$, the edge colours are distinct and none equals $2i$; the colour of $ij$ differs from $2j$ as well. This proves the exact value $n+1$. The same construction on all $q$ vertices gives $\chi''(K_q)=q$ for odd $q\geq3$.

4. Adversarial check and the unresolved step

The tree construction fails on a graph with cycles because a newly coloured vertex can already have several coloured neighbours, and a newly processed edge can impose constraints at both ends. Treating those extra conflicts as absent would be an invalid proof. Conversely, the complete-graph test rules out replacing the target by $\Delta+1$. The accompanying diagnostic checks every incidence in the modular construction for complete graphs of orders 2 through 30 and checks the tree construction on every labelled tree through six vertices. These are implementation checks of the constructions, not evidence covering all graphs. A method that coordinates the two endpoint constraints using only $\Delta+2$ colours in an arbitrary graph is still missing.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1165 (GT-010), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 R. Su, G. Fang and E. Zhu, The Total Coloring Conjecture holds for planar graphs without three special subgraphs, arXiv:2507.12737 $2025$. https://arxiv.org/abs/2507.12737. Bibliographic information from the supplied record.