Polynomial-time precoloring extension for bounded outer faces
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 , consider instances whose outer face has length at most .
Polynomial-time precoloring-extension conjecture. For every positive integer , there is a polynomial-time algorithm that, given a planar near-Eulerian-triangulation with outer face of length at most and a precoloring of the vertices incident with the outer face, decides whether extends to a 4-coloring of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.