Precoloring extension for sufficiently generic near-Eulerian triangulations

Let \ell be a positive even integer. A planar near-Eulerian-triangulation is a planar graph with triangular bounded faces and even vertex degrees. Let GG have outer face bounded by a cycle CC of length \ell, and let UU be an independent set disjoint from CC such that GUG-U is bipartite. Let SS be a set of dd faces of GUG-U, each of length at least six. A 4-coloring of CC is viable if it satisfies the viability condition defined in the source.

Generic precoloring-extension conjecture. For every positive even integer \ell, there exists an integer dd such that, if no 4-cycle in GUG-U separates a face of SS from the outer face, and for distinct faces s1,s2Ss_1,s_2\in S the distance between s1s_1 and s2s_2 in GUG-U is at least dd and no closed walk of length less than \ell in GUG-U separates both s1s_1 and s2s_2 from the outer face, then any viable 4-coloring of CC extends to a 4-coloring of GG.

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

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.