Precoloring extension for sufficiently generic near-Eulerian triangulations

About 3 years old · traced to

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 G−UG-U is bipartite. Let SS be a set of dd faces of G−UG-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 G−UG-U separates a face of SS from the outer face, and for distinct faces s1,s2∈Ss_1,s_2\in S the distance between s1s_1 and s2s_2 in G−UG-U is at least dd and no closed walk of length less than ℓ\ell in G−UG-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.

References

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.