A Rooted Structure Theorem for -Connected Graphs and -Minors
En palabras de los autores
Jorgensen conjectured that every -connected graph with no -minor is apex. For a -connected graph containing a on vertices , being apex is equivalent to having a planar embedding with the other three roots on a common face for some , so that for such graphs the conjecture becomes a rooted planarity statement. Robertson, Seymour, and Thomas showed that the failure of the corresponding three-rooted planarity is witnessed by a legless tripod. We introduce a four-root structure, called a frame, that extends this certificate, and prove a structural theorem: every -connected graph containing a frame rooted at four prescribed vertices contains a subgraph of one of five explicit types, denoted --. This theorem does not depend on the edges among the roots. As an application, we show that when the four roots span a , each of the five configurations yields a -minor. Together with a planar argument for the case without a frame and an induction based on a theorem of Kawarabayashi, this gives a proof that every non-planar -connected graph contains a -minor. This statement also follows from a recent theorem of Lo; our proof is independent and is driven by the rooted structure theorem, whose method we expect to apply to Jorgensen's conjecture with other target configurations.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 30 pages, 12 figures