Open Problem Garden

For , the class of graphs with no minor is very well understood. Simple graphs without minors are forests. Graphs without minors are called series-parallel graphs, and have a simple construction. Finally, Wagner [W] obtained a construction for all graphs without minors. For , an explicit characterization of those graphs without 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 -minor suggest interesting properties of highly connected graphs without minors which appear quite difficult to resolve.

Part of the interest in graphs without minors stems from Hadwiger's conjecture (every loopless graph without a minor is -colorable). Indeed, Wagner's work on graphs with no minor was done while studying the case of Hadwiger. More recently, Robertson, Seymour, and Thomas [RST] proved Hadwiger's conjecture for , 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 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].