4-coloring extension via well-separated long faces

Conjecture 4 · arXiv:2312.13061

arXiv Conjecture high confidence— first stated 2023-12-20

Authors: Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová, Robert Šámal

Status open high confidence

Conjecture 4 from arXiv:2312.13061 posits a sufficient structural condition (sufficiently many well-separated long faces in G-U, a bipartite subgraph) under which every viable 4-coloring of the outer cycle extends to a full 4-coloring of a planar near-Eulerian-triangulation. The source paper was subsequently published as a journal article in the European Journal of Combinatorics 127 (2025), 104138, but this is the same work. No follow-up paper proving or disproving this conjecture was found in the indexed literature.

Reviewer notes. The source paper was published as European Journal of Combinatorics 127 (2025) 104138 (same title, same authors — journal version only). A second EJC entry (vol. 129, 104183) by the same authors may be a corrigendum or companion piece. The related paper arXiv:2409.19165 (four-coloring Eulerian triangulations of the torus, Brianski–Kral–Lamaison–Shu) does not address this conjecture. No paper specifically resolving Conjecture 4 was found after a wide web search.

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

Conjecture. For every positive even integer $\ell$, there exists an integer $d$ such that the following claim holds. Let $G$ be a planar near-Eulerian-triangulation with the outer face bounded by a cycle $C$ of length $\ell$ and let $U$ be an independent set disjoint from $C$ such that $G-U$ is bipartite. Moreover, suppose that $G-U$ has a set $S$ of $d$ faces of length at least six such that there is no 4-cycle in $G-U$ separating a face of $S$ from the outer face, and for distinct faces $s_{1},s_{2}\in S$, the distance between $s_{1}$ and $s_{2}$ in $G-U$ is at least $d$ and there is no closed walk of length less than $\ell$ in $G-U$ separating both $s_{1}$ and $s_{2}$ from the outer face. Then any viable 4-coloring of $C$ extends to a 4-coloring of $G$.

Context

This conjecture captures a 'sufficiently generic' structural condition under which the necessary topological condition for precoloring extension is also sufficient. It is posed as an intermediate step toward Conjecture 3, asserting that when $G-U$ is bipartite and contains sufficiently many well-separated long faces, every viable precoloring of the outer face extends to a full 4-coloring.

Source paper

Precoloring extension in planar near-Eulerian-triangulations
Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová, Robert Šámal · 2023-12-20
https://arxiv.org/abs/2312.13061