Conflict k-colouring on surfaces of genus g

Conjecture 3 · arXiv:1803.10962

arXiv Conjecture high confidence— first stated 2020-10-09

Authors: Zdeněk Dvořák, Louis Esperet, Ross J. Kang, Kenta Ozeki

Status open high confidence

Conjecture 3 from arXiv:1803.10962 asserts a Heawood-type threshold for single-conflict colouring on surfaces: conflict k-colourability holds for graphs on a surface of Euler genus g when k ≥ C'√g and each edge carries at most Ck conflicts. The source paper itself establishes an O(√g log g) upper bound in this regime, leaving a logarithmic gap. A follow-up by Bradshaw and Masařík (arXiv:2112.06333, JGT 2025) resolves a separate question from the same paper concerning degenerate graphs but does not address Conjecture 3 for surfaces. No resolution of Conjecture 3 was found in the indexed literature.

Cited literature (1)

partial Single-conflict colorings of degenerate graphs (2025)

Peter Bradshaw, Tomáš Masařík · Journal of Graph Theory · arXiv:2112.06333

Proves χ≠(G) = O(√d log n) for simple d-degenerate graphs, answering Question 1.5 of Dvořák–Esperet–Kang–Ozeki, but does not address Conjecture 3 about graphs embeddable on surfaces.

Reviewer notes. Conjecture 3 was adjusted in v2 of the source paper (October 2020); the surrounding context specifies that C < 1/2 is forced by an instructive example, and a previous version incorrectly allowed C arbitrarily close to 1. The Bradshaw–Masařík paper (2112.06333) is the only confirmed post-2020 follow-up to the source paper, but it targets a different open problem (degenerate graphs). No paper resolving the surface-specific Conjecture 3 was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There exist $C, C' > 0$ such that, for any simple graph $G$ that is embeddable on a surface of Euler genus $g$, if every edge is assigned at most $Ck$ conflicts from $[k]^2$, then $G$ is conflict $k$-colourable, provided $k \geq C'\sqrt{g}$.

Context

Theorem 1 gives an upper bound of the form $\chi_=(G) = O(\sqrt{g}\log g)$ in the $\mu = \Theta(\sqrt{g})$ regime, evocative of Heawood's bound. The authors note that $C < 1/2$ is forced by their second instructive example, and that a previous version of the manuscript incorrectly conjectured $C$ could be taken arbitrarily close to 1.

Source paper

Single-conflict colouring
Zdeněk Dvořák, Louis Esperet, Ross J. Kang, Kenta Ozeki · 2020-10-09
https://arxiv.org/abs/1803.10962 PDF source