Zhang et al.'s AVD total coloring conjecture

Let GG be a finite, simple, undirected graph. For each vertex uu, let NG(u)N_G(u) be its set of neighbours, let G(u)\partial_G(u) be the set of edges incident with uu, and let G(u)={u}G(u)\partial_G^\star(u)=\{u\}\cup\partial_G(u). Write Δ(G)\Delta(G) for the maximum degree of GG. An adjacent vertex distinguishing (AVD) total coloring is a proper total coloring ϕ:V(G)E(G)C\phi:V(G)\cup E(G)\to C such that ϕ(G(u))ϕ(G(v))\phi(\partial_G^\star(u))\ne\phi(\partial_G^\star(v)) for every edge uvE(G)uv\in E(G). AVD Total Coloring Conjecture. Every graph GG has an AVD total coloring using at most Δ(G)+3\Delta(G)+3 colors.

The conjecture is a strengthening of the total coloring problem, requiring adjacent vertices to have distinct sets of colors on their incident vertices and edges. The source attributes it to Zhang et al.; the supplied text does not establish whether it is resolved in full.

Sources & referencesView supporting material

Primary source

Diptimaya Behera, Mathew C. Francis and Sreejith K. Pallathumadam, “Adjacent vertex distinguishing total coloring of 3-degenerate graphs”, arXiv:2508.03549 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.