Polynomial-time precoloring extension in planar near-Eulerian-triangulations

Conjecture 3 · 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 3 — that for every fixed $\ell$ there is a polynomial-time algorithm deciding precoloring extension to a 4-coloring in planar near-Eulerian-triangulations with outer face of length at most $\ell$ — remains open. The source paper, published in the European Journal of Combinatorics in 2025 (Vol. 127, art. 104138), resolves only the special cases of outer face length at most five and the case where all outer-face vertices have odd degree and the precoloring uses only three colors. No subsequent paper proving or disproving the general conjecture was found in the literature as of May 2026.

Reviewer notes. The full paper appeared as European Journal of Combinatorics 127 (2025) 104138. An extended abstract was published at EUROCOMB'23. No follow-up paper proving Conjecture 3 (the general polynomial-time case) was found in three targeted searches. The conjecture is likely still open; confidence is high given the paper is recent (< 3 years) and the problem is technically demanding.

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

Conjecture. For every positive integer $\ell$, there is a polynomial-time algorithm that given a planar near-Eulerian-triangulation $G$ with the outer face of length at most $\ell$ and a precoloring $\varphi$ of the vertices incident with the outer face decides whether $\varphi$ extends to a 4-coloring of $G$.

Context

The paper provides only a necessary topological condition for precoloring extension in general, and resolves the problem completely only for outer faces of length at most five and in the case where all vertices of the outer face have odd degree and are colored with three colors. The authors conjecture that combining the topological condition with further ideas will resolve the disk case in full, and that a polynomial-time decision algorithm exists for any fixed outer face length $\ell$.

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