The subcontraction conjecture for facial 3-colorability and 3-flows
Let be a graph. A graph is facially -colorable if it has a facial -coloring, and -flowable if it admits a nowhere-zero -flow. For , let be the graph obtained from by joining two vertices in its partite set of size by an edge; a subcontraction is the graph operation used in the paper's definition.
The subcontraction conjecture. If is a facially -colorable graph which does not have a subcontraction isomorphic to for some , then is -flowable.
A positive answer would establish facial -colorability and -flowability as equivalent for graphs excluding the displayed obstructions as subcontractions. The paper proves this equivalence for graphs of maximum degree at most and for -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
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.