Precoloring extension for sufficiently generic near-Eulerian triangulations
Precoloring extension for sufficiently generic near-Eulerian triangulations
Let be a positive even integer. A planar near-Eulerian-triangulation is a planar graph with triangular bounded faces and even vertex degrees. Let have outer face bounded by a cycle of length , and let be an independent set disjoint from such that is bipartite. Let be a set of faces of , each of length at least six. A 4-coloring of is viable if it satisfies the viability condition defined in the source.
Generic precoloring-extension conjecture. For every positive even integer , there exists an integer such that, if no 4-cycle in separates a face of from the outer face, and for distinct faces the distance between and in is at least and no closed walk of length less than in separates both and from the outer face, then any viable 4-coloring of extends to a 4-coloring of .
This conjecture proposes a sufficient condition for extending viable boundary colorings in sufficiently generic instances, and is presented as a step toward the bounded-boundary-length precoloring-extension conjecture. The definition of viability is deferred to the source, and no resolution is given.
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.