Jorgensen's Conjecture

Importance: High ✭✭✭
Author(s): Jorgensen, Leif K.
Keywords: connectivity
Recomm. for undergrads: no
Prize: none
Posted by: mdevos
on: March 10th, 2007
Conjecture   Every 6-connected graph without a $ K_6 $ minor is apex (planar plus one vertex).

For $ n \le 5 $, the class of graphs with no $ K_n $ minor is very well understood. Simple graphs without $ K_3 $ minors are forests. Graphs without $ K_4 $ minors are called series-parallel graphs, and have a simple construction. Finally, Wagner [W] obtained a construction for all graphs without $ K_5 $ minors. For $ n \ge 6 $, an explicit characterization of those graphs without $ K_n $ minors appears hopeless. The graph minors project of Robertson and Seymour give a rough structure theorem for such classes, but much remains unknown. In particular, this conjecture and Thomas' conjecture highly connected graphs with no $ K_n $-minor suggest interesting properties of highly connected graphs without $ K_n $ minors which appear quite difficult to resolve.

Part of the interest in graphs without $ K_n $ minors stems from Hadwiger's conjecture (every loopless graph without a $ K_{n+1} $ minor is $ n $-colorable). Indeed, Wagner's work on graphs with no $ K_5 $ minor was done while studying the $ n=4 $ case of Hadwiger. More recently, Robertson, Seymour, and Thomas [RST] proved Hadwiger's conjecture for $ n=5 $, and in doing so came somewhat close to proving Jorgensoen's conjecture. The thrust of their argument is to prove that any minimal counterexample to Hadwiger for $ n=5 $ is apex. However, in doing so, they exploit both connectivity and coloring properties of a minimal counterexample. It would appear to be difficult to modify their argument to prove Jorgensen's conjecture.

DeVos, Hegde, Kawarabayashi, Norine, Thomas, and Wollan proved this conjecture true for all sufficiently large graphs [KNTWa,KNTWb].


[RST] N. Robertson, P. D. Seymour, R. Thomas, Hadwiger's conjecture for $ K\sb 6 $-free graphs. Combinatorica 13 (1993), no. 3, 279-361. MathSciNet

[W] K. Wagner Uber eine Eigenschaft der ebenen Komplexe, Math. Ann 114 (1937) 570-590. MathSciNet

[KNTWa] Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan. $ K_6 $ minors in 6-connected graphs of bounded tree-width. J. Combinatorial Theory, Series B, 136:1--32, 2019

[KNTWb] Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan. $ K_6 $ minors in large 6-connected graphs. J. Combinatorial Theory, Series B, 129:158-203, 2019.

* indicates original appearance(s) of problem.