The improper 4-coloring conjecture for toroidal graphs with defect sequence
The improper 4-coloring conjecture for toroidal graphs with defect sequence
A toroidal graph is a graph that can be embedded on the torus. A coloring is -improper when the vertices are partitioned into four color classes such that the first three induce graphs of maximum degree , while the fourth induces a graph of maximum degree at most .
Improper coloring conjecture for toroidal graphs. Every toroidal graph is -colorable.
The paper proves this property for every not -degenerate toroidal graph, so any counterexample would have to be -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.