Largest minor-closed class dichromatic number 2
Question 1 · arXiv:1907.00351
Status open high confidence
Question 1 asks for the largest minor-closed class of undirected graphs with dichromatic number at most 2. The source paper itself establishes that this class lies strictly between K_5-minor-free and K_7-minor-free graphs: K_5-minor-free graphs are contained in it (conditional on the Neumann-Lara–Škrekovski conjecture for planar digraphs), while K_{3,3}-minor-free graphs are not. No subsequent paper has been found that resolves the exact boundary. Steiner's follow-up work (2021–2022) addresses complete minors in digraphs and dichromatic subdivisions but does not settle this specific question.
Reviewer notes. No follow-up paper resolving Question 1 was found in 5 web calls. The question of identifying the largest minor-closed class G_2 of undirected graphs with dichromatic number at most 2 remains open as of 2026-05-15. The paper was published in DMTCS 22(4) #11 (2021). Related work by Steiner (arXiv:2101.04590, arXiv:2008.09888) addresses complete minors and subdivisions in digraphs with given dichromatic number but does not directly address Question 1.
Context
The authors note that while $\vec{\chi}(K_6) = 2$ and $\vec{\chi}(K_7) = 3$, so $\mathcal{G}_2$ is a subclass of the $K_7$-minor-free graphs, it seems to be much smaller: there exist $K_{3,3}$-minor-free graphs with dichromatic number greater than 2.
Source paper
A Note on Graphs of Dichromatic Number 2
Raphael Steiner · 2019-06-30
https://arxiv.org/abs/1907.00351
PDF source