Borodin–Kostochka–Woodall List Total Coloring Conjecture

Let GG be a graph, and let T(G)T(G) be its total graph, whose vertices are the vertices and edges of GG, with adjacency given by adjacency, incidence, or edge adjacency in GG. The source also writes T(G)=B(G)2T(G)=B(G)^2. Write χ\chi for chromatic number and χ\chi_\ell for list chromatic number. Borodin–Kostochka–Woodall List Total Coloring Conjecture. Every graph GG satisfies

χ(T(G))=χ(T(G)).\chi(T(G))=\chi_\ell(T(G)).

This conjecture is a special case of the stronger List Square Coloring Conjecture, which has been refuted by Kim and Park; consequently, the total-coloring conjecture is refuted as stated.

Sources & referencesView supporting material

Primary source

Morteza Hasanvand, “The List Square Coloring Conjecture fails for bipartite planar graphs and their line graphs”, arXiv:2211.00622 (2025).

Additional references

2 papers in this index state this conjecture (2013–2022). The statement above is taken from the most recent of them; the others are arXiv:1305.2566.

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.