The subcontraction conjecture for facial 3-colorability and 3-flows
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.
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
Sign in to submit a solution.
No solutions have been posted yet.