The correspondence coloring conjecture for -minor-free graphs
The correspondence coloring conjecture for -minor-free graphs
Let ) be a -minor-free graph, and let be a correspondence -cover of . A collection of colorings is disjoint if they are pairwise disjoint as -colorings.
Correspondence coloring conjecture. The graph has disjoint -colorings. Equivalently,
where is the class of all -minor-free graphs and denotes the disjoint correspondence coloring number.
The best known upper bound is , so the conjecture would determine the first open case after -minor-free graphs. It is motivated by the known bounds for smaller excluded cliques and by the fact that every -minor-free graph has maximum average degree less than .
Sources & referencesView supporting material
Primary source
Wouter Cames van Batenburg, Daniel W. Cranston and František Kardoš, “Disjoint Correspondence Colorings for K_5-Minor-free Graphs”, arXiv:2602.16692 (2026).
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.