For every simple graph G, the adjacent vertex distinguishing total chromatic number satisfies chi''_a(G)≤ Delta(G)+3. Here, chi''_a(G) is the least integer k such that G has a proper total coloring f with at most k colors and C_G(u)≠ C_G(v) for every edge uv∈ E(G), where C_G(u)=f(u)cupf(uw):uw∈ E(G).

Adjacent vertex distinguishing total coloring conjecture

The conjecture, proposed by Zhang, Chen, Li, Yao, Lu, and Wang in 2005, asserts that every simple graph $G$ admits an adjacent-vertex-distinguishing total coloring with at most $\Delta(G)+3$ colors.

Known results

The bound holds for all $2$ -degenerate graphs (Miao, Shi, Hu, and Luo, 2016).
It is claimed for all $3$ -degenerate graphs in a preprint dated August 5, 2025.
It is known for several families, including complete, bipartite, outerplanar, split, and suitable planar graphs.
For general graphs with $\Delta(G)>2$ , the established upper bound is $\chi_a''(G)\le 2\Delta(G)$ (Huang, Wang, and Yan, 2012).

September 2026 graph-product extension

A new paper claims $\chi_a''(G)\le\Delta(G)+3$ for multiple classes of graph products, extending the known range but not proving the conjecture for arbitrary simple graphs. This class-specific advance has not been independently verified in the retrieved sources.

Current status (as of September 2026): The conjecture is proved or claimed for many graph classes, including several graph products, but remains open for arbitrary simple graphs.

Adjacent vertex distinguishing total coloring conjecture

Primary source

Additional references

Progress summary

Solutions 0