Planar near-cubic 5-distance coloring cone membership
Conjecture 8 · arXiv:1907.04066
Status open high confidence
Conjecture 8 from arXiv:1907.04066 asserts that every plane near-cubic graph $\tilde{G}$ with $d(\tilde{G})=5$ has its coloring-count vector $n_{\tilde{G}}$ in the subcone $B'_5$, making it a strict strengthening of the Four Color Theorem. The authors verified it computationally for all such graphs with fewer than 30 vertices and showed that every counterexample must contain one of 38 specific graphs as a minor. No subsequent paper resolving or substantially advancing the conjecture was found in a wide search of the literature through May 2026.
Reviewer notes. No follow-up paper resolving Conjecture 8 was found. The paper was published in the Journal of Graph Theory in 2022 (doi listed on Wiley: 10.1002/jgt.22767). Semantic Scholar returned zero indexed citations. The conjecture remains open as a strict strengthening of the Four Color Theorem; the main computational evidence is the verification for graphs with fewer than 30 vertices and the minor-obstruction characterization (38 graphs).
Context
The cone $B'_5$ is defined as the subcone of $B_5$ spanned by the rays $\operatorname{ray}(\tilde{R}_{5,1}), \ldots, \operatorname{ray}(\tilde{R}_{5,11})$, excluding the ray corresponding to the non-planar graph $\tilde{R}_{5,12}$. By Lemma 7, membership of $n_{\tilde{G}}$ in the full cone $B_5$ is equivalent to the Four Color Theorem, so this conjecture is a strict strengthening of the Four Color Theorem. The authors verify it for all plane near-cubic graphs with fewer than 30 vertices.
Also stated in
- Coloring count cones of planar graphs (2021-10-25)
Notes. PDF source — math may be garbled
Source paper
Coloring count cones of planar graphs
Zdeněk Dvořák, Bernard Lidický · 2021-10-25
https://arxiv.org/abs/1907.04066
PDF source