Forcing a $K_6$-minor

Medium ★★ Graph Theory » Basic Graph Theory » Minors

Authors: Barát ,János, Joret, Gwenaël, Wood, David R.— posted by David Wood on 2012-01-16

Status partial medium confidence

Both Barát-Joret-Wood conjectures (every graph with minimum degree $\geq 7$ contains a $K_6$ minor; every 7-connected graph contains a $K_6$ minor) remain open in general. The 7-connected version is known to hold for sufficiently large graphs via the Kawarabayashi-Norine-Thomas-Wollan proof of Jørgensen's conjecture for large graphs (papers posted shortly after the OPG entry, formally published in 2018). Chudnovsky, Scott, Seymour and Spirkl (2024) proved the bipartite analogue: every bipartite graph with minimum degree $\geq 6$ has a $K_6$ minor.

Cited literature (3)

partial K_6 minors in large 6-connected graphs (2018)

Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan · Journal of Combinatorial Theory, Series B · arXiv:1203.2192 · doi:10.1016/j.jctb.2017.09.007

Proves Jørgensen's conjecture for all sufficiently large graphs: every sufficiently large 6-connected graph with no $K_6$ minor is apex; this implies the 7-connected $K_6$-minor conjecture for sufficiently large graphs.
partial K_6 minors in 6-connected graphs of bounded tree-width (2018)

Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan · Journal of Combinatorial Theory, Series B · arXiv:1203.2171 · doi:10.1016/j.jctb.2017.09.006

Companion paper proving that every sufficiently large 6-connected graph of bounded tree-width with no $K_6$ minor is apex, a key step toward the large-graph Jørgensen result.
partial Bipartite graphs with no $K_6$ minor (2024)

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · Journal of Combinatorial Theory, Series B · arXiv:2204.10119 · doi:10.1016/j.jctb.2023.08.005

Proves a bipartite analogue of the Barát-Joret-Wood minimum-degree conjecture: every bipartite graph with minimum degree at least 6 contains a $K_6$ minor; explicitly notes that the original conjecture (minimum degree 7 forces $K_6$) remains open.

Reviewer notes. The KNTW arXiv papers (1203.2171, 1203.2192) were posted 2012-03-09, after the OPG posted date 2012-01-16, so they qualify as post-posting. They formally appeared in JCTB Series B vol. 129 (2018). Both original conjectures remain open: the 7-connected version is settled only for sufficiently large graphs, and the minimum-degree-7 version has no known proof. The Chudnovsky-Scott-Seymour-Spirkl paper explicitly states 'we do not know whether all graphs with minimum degree at least seven have $K_6$ minors,' confirming the conjecture is open as of 2024.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Conjecture. Every graph with minimum degree at least 7 contains a $ K_6 $ -minor.

Conjecture. Every 7-connected graph contains a $ K_6 $ -minor.

Keywords: connectivity · graph minors

Discussion

The first conjecture implies the second. Whether the second conjecture is true was first asked in [KT]. Both conjectures were stated in [BJW]. The second conjecture is implied by Jørgensen’s conjecture , which asserts that every $ 6 $ -connected $ K_6 $ -minor-free graph is apex (which have minimum degree at most $ 6 $ and are thus not $ 7 $ -connected). Since Jørgensen’s conjecture is true for sufficiently large graphs [KNTWa,KNTWb], the second conjecture is true for sufficiently large graphs.

Bibliography

★ [BJW] János Barát, Gwenaël Joret, David R. Wood. Disproof of the List Hadwiger Conjecture, Electronic J. Combinatorics 18:P232, 2011.
★ [KT] Ken-ichi Kawarabayashi and Bjarne Toft. Any 7-chromatic graph has $ K_7 $ or $ K_{4,4} $ as a minor. Combinatorica 25 (3), 327–353, 2005.
[KNTWa] Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan. $ K_6 $ minors in $ 6 $ -connected graphs of bounded tree-width. http://arxiv.org/abs/1203.2171
[KNTWb] Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan. $ K_6 $ minors in large $ 6 $ -connected graphs. http://arxiv.org/abs/1203.2192