4-coloring extension for near-triangulations

Problem 1 · arXiv:1907.04066

arXiv Problem high confidence— first stated 2021-10-25

Authors: Zdeněk Dvořák, Bernard Lidický

Status partial high confidence

Problem 1 asks whether a polynomial-time algorithm exists to decide if a 4-coloring of the outer 4-cycle of a near-triangulation extends to the whole graph; the general question remains open. Dvořák, Moore, Seifrtová, and Šámal (arXiv:2312.13061) provide partial progress by giving linear-time algorithms for the special subclass of planar near-Eulerian-triangulations (all interior vertices have even degree) when the outer face has length at most 5, which covers the 4-cycle case within that restricted class. No resolution of the full statement for arbitrary near-triangulations was found in the literature.

Cited literature (1)

partial Precoloring extension in planar near-Eulerian-triangulations (2023)

Dvořák, Moore, Seifrtová, Šámal · arXiv preprint · arXiv:2312.13061

Gives linear-time algorithms for 4-precoloring extension in planar near-Eulerian-triangulations with outer face length at most 5 (including the 4-cycle case), constituting a special-case resolution of Problem 1 restricted to the Eulerian interior-degree setting.

Reviewer notes. The paper arXiv:2312.13061 addresses a strictly more restricted class (near-Eulerian-triangulations, where all interior vertices have even degree) rather than arbitrary near-triangulations. Its Conjecture 3 further conjectures a polynomial-time algorithm for all bounded outer-face lengths in the near-Eulerian setting, suggesting the general Problem 1 is still open. A 2025 European Journal of Combinatorics paper (vol. 127, art. 104138) appears related but its content could not be verified via WebFetch.

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

Problem. Does there exist a polynomial-time algorithm which, given a near-triangulation $G$ with the outer face bounded by a 4-cycle $C$ and a 4-coloring $\psi$ of $C$, correctly decides whether $\psi$ extends to a 4-coloring of $G$?

Context

The authors note that even very basic precoloring extension questions for planar graphs are wide open. There exist infinitely many near-triangulations $G$ whose outer 4-cycle has a precoloring that does not extend to a 4-coloring of $G$, yet no good characterization of such graphs is known.

Notes. PDF source — math notation 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