Polynomial-time precoloring extension for bounded outer faces

A planar near-Eulerian-triangulation is a planar graph in which every bounded face is a triangle and every vertex has even degree; a precoloring assigns colors from a set of four colors to the vertices incident with the outer face. For a positive integer \ell, consider instances whose outer face has length at most \ell.

Polynomial-time precoloring-extension conjecture. For every positive integer \ell, there is a polynomial-time algorithm that, given a planar near-Eulerian-triangulation GG with 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 GG.

This conjecture extends the proved linear-time result for outer faces of length at most five and would resolve the disk case for every fixed boundary length. The source gives no resolution beyond these bounded-length results.

Sources & referencesView supporting material

Primary source

Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová and Robert Šámal, “Precoloring extension in planar near-Eulerian-triangulations”, arXiv:2312.13061 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.