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

From papers

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 n4n\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 n4n\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.