3-flowability via K⁺₃,ₙ₋₃-free subcontraction

Conjecture 11 · arXiv:2008.09692

arXiv Conjecture high confidence— first stated 2022-08-26

Authors: Christoph Hertrich, Felix Schröder, Raphael Steiner

Status open high confidence

No follow-up paper specifically proving or disproving Conjecture 11 was found in the literature. The conjecture is closely entangled with the open Tutte 3-Flow Conjecture (a positive resolution of Conjecture 11 would imply Tutte's conjecture), placing it among the hardest open problems in flow theory. The original paper established the conjecture for subcubic graphs and for K_{3,3}-minor-free graphs; no extension of these partial results has been identified.

Reviewer notes. Semantic Scholar lists one post-2022 citing paper (Weinberger & Zeng, arXiv:2603.05208, 2026) but its abstract makes no mention of cell 3-colorability, 3-flowability, or Conjecture 11; it concerns plane structures in complete-graph drawings and is not relevant to this conjecture. The conjecture's connection to Tutte's 3-Flow Conjecture (itself wide open) suggests it is unlikely to have been resolved quietly.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. If $G$ is a universally cell 3-colorable graph which does not have a subcontraction isomorphic to $K^+_{3,n-3}$ for some $n \geq 7$, then $G$ is 3-flowable.

Context

The paper exhibits an infinite family of universally cell 3-colorable graphs ($K^+_{3,n-3}$ for $n \geq 7$) that do not admit a nowhere-zero 3-flow, showing the two properties are not equivalent in general. The authors believe excluding these graphs as subcontractions is sufficient to recover equivalence between universal cell 3-colorability and 3-flowability. Remarkably, a positive resolution of this conjecture would also imply Tutte's 3-Flow Conjecture.

Source paper

Coloring Drawings of Graphs
Christoph Hertrich, Felix Schröder, Raphael Steiner · 2022-08-26
https://arxiv.org/abs/2008.09692 PDF source