The improper 4-coloring conjecture for toroidal graphs with defect sequence (0,0,0,3)(0,0,0,3)

A toroidal graph is a graph that can be embedded on the torus. A coloring is (0,0,0,3)(0,0,0,3)-improper when the vertices are partitioned into four color classes such that the first three induce graphs of maximum degree 00, while the fourth induces a graph of maximum degree at most 33.

Improper coloring conjecture for toroidal graphs. Every toroidal graph is (0,0,0,3)(0,0,0,3)-colorable.

The paper proves this property for every not 55-degenerate toroidal graph, so any counterexample would have to be 55-degenerate. The conjecture is presented as open; it would sharpen the known improper-coloring results for toroidal graphs.

Sources & referencesView supporting material

Primary source

Alexandra Kolačkovská, Mária Maceková, Roman Soták and Diana Švecová, “Improper coloring of toroidal graphs”, arXiv:2509.15870 (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.