The subcontraction conjecture for facial 3-colorability and 3-flows

About 6 years old · traced to

Let GG be a graph. A graph is facially 33-colorable if it has a facial 33-coloring, and 33-flowable if it admits a nowhere-zero 33-flow. For n≥4n\geq 4, let K3,n+K_{3,n}^+ be the graph obtained from K3,nK_{3,n} by joining two vertices in its partite set of size 33 by an edge; a subcontraction is the graph operation used in the paper's definition.

The subcontraction conjecture. If GG is a facially 33-colorable graph which does not have a subcontraction isomorphic to K3,n+K_{3,n}^+ for some n≥4n\geq 4, then GG is 33-flowable.

A positive answer would establish facial 33-colorability and 33-flowability as equivalent for graphs excluding the displayed obstructions as subcontractions. The paper proves this equivalence for graphs of maximum degree at most 33 and for K3,3K_{3,3}-minor-free graphs, but the general assertion remains open.

References

Primary source

Christoph Hertrich, Felix Schröder and Raphael Steiner, “Coloring Drawings of Graphs”, arXiv:2008.09692 (2022).

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.