Jørgensen's Conjecture: is every 6-connected graph with no K_6 minor apex?
Statement
A graph $H$ is a *minor* of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. A graph is *apex* if deleting some single vertex leaves a planar graph. Jørgensen (1994) conjectured that **every $6$-connected graph with no $K_6$ minor is apex**. Decide the conjecture, or exhibit a $6$-connected $K_6$-minor-free graph that is not apex. Computational sub-question: verify the conjecture for all $6$-connected graphs up to $n$ vertices.
Acceptance. FULLY RESOLVES: a $6$-connected $K_6$-minor-free non-apex graph, with a certificate that it has no $K_6$ minor (a rooted-minor/branch-decomposition test) and that deleting any single vertex still leaves a non-planar graph (a planarity test per vertex), refuting the conjecture; or a proof. PARTIAL PROGRESS: an exhaustive verification, via $\texttt{nauty}$, that every $6$-connected graph on at most $n$ vertices with no $K_6$ minor is apex. Provide the minor test, per-vertex planarity check, and enumeration bound.
Background
Frontier: the conjecture refines the structure behind Hadwiger's conjecture for $t = 6$ (the case $K_6$-minor-free graphs are $5$-colorable, reduced by Robertson, Seymour & Thomas to the Four Color Theorem). Kawarabayashi, Norin, Thomas & Wollan proved Jørgensen's conjecture for all *sufficiently large* graphs (arXiv:1203.2192, 'K_6 minors in large 6-connected graphs'), leaving the small cases open. Source: Open Problem Garden, 'Jorgensen's Conjecture' (www.openproblemgarden.org/op/jorgensens_conjecture), originator L. K. Jørgensen.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Jorgensen's Conjecture — Open Problem Garden | link |
| REF-02 | Kawarabayashi, Norin, Thomas, Wollan, K_6 minors in large 6-connected graphs (2012) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.