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

\begin{conjecture} Every 6-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_6$]{complete graph} \Def[minor]{minor (graph theory)} is apex (planar plus one vertex). \end{conjecture}

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 \Def[series-parallel graphs]{series-parallel graph}, 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 \OPref[highly connected graphs with no $K_n$-minor]{high_connectivity_no_k_n} 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.

Recently, DeVos, Hegde, Kawarabayashi, Norine, Thomas, and Wollan proved this conjecture true for all sufficiently large graphs.


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

[W] K. Wagner Uber eine Eigenschaft der ebenen Komplexe, Math. Ann 114 (1937) 570-590. \MRhref{1513158}

* indicates original appearance(s) of problem.