√d log n bound for degenerate single-conflict chromatic number

Informal conjecture on single-conflict chromatic number of degenerate graphs · arXiv:1803.10962

arXiv Informal medium confidence— first stated 2020-10-09

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

Status solved high confidence

Bradshaw and Masařík (arXiv:2112.06333) proved that the single-conflict chromatic number of any simple d-degenerate graph G satisfies χ↮(G) ≤ ⌨12√(d(1+log((d+1)Δ))⌉, which is O(√d·log n), directly answering Question 1.5 posed by Dvořák, Esperet, Kang, and Ozeki. This resolves the conjecture in the simple-graph (μ=1) case, which is precisely the case discussed in the surrounding context concerning the μ=1 instance of Theorem 1. The paper was subsequently published in the Journal of Graph Theory (2025, DOI 10.1002/jgt.23025).

Cited literature (1)

proof Single-conflict colorings of degenerate graphs (2021)

Peter Bradshaw, Tomáš Masařík · Journal of Graph Theory · arXiv:2112.06333 · doi:10.1002/jgt.23025

Proves χ↮(G) = O(√d·log n) for simple d-degenerate graphs on n vertices (Theorem 1.7), explicitly answering the conjecture (Question 1.5) of Dvořák, Esperet, Kang, and Ozeki.

Reviewer notes. The conjecture is fully resolved for simple graphs (μ=1), which is the case stated in the surrounding context. Bradshaw–Masařík also handle multigraphs with edge-multiplicity at most log log n. The arXiv preprint appeared December 2021; journal publication in Journal of Graph Theory is listed as 2025.

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

Informal. There might yet be some constant $C' > 0$ such that the single-conflict chromatic number of any $d$-degenerate graph on $n$ vertices is at most $C'\sqrt{d}\log n$.

Context

The authors discuss whether degeneracy could serve as an alternative approach to proving Theorem 1 in the $\mu = 1$ case, analogous to Heawood's original method. They note that a construction of Kostochka and Zhu shows $d$-degenerate graphs can have single-conflict chromatic number greater than $d$, but the bound $C'\sqrt{d}\log n$ would still imply the $\mu = 1$ case of Theorem 1; Theorem 4 gives the weaker bound $C_2(nd)^{1/4}\log(nd)$.

Notes. Stated as 'there might yet be' and 'we have not been able to prove this thus far'; clearly conjectural but not a labelled environment.

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