Minors of two-connected graphs of large path-width

2017/12/12 by Thanh Dang, Robin Thomas, Dang, Thanh N. +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1712.04549

Abstract

Let P be a graph with a vertex v such that P\backslash v is a forest, and let Q be an outerplanar graph. We prove that there exists a number p=p(P,Q) such that every 2-connected graph of path-width at least p has a minor isomorphic to P or Q. This result answers a question of Seymour and implies a conjecture of Marshall and Wood. The proof is based on a new property of tree-decompositions.

Related

• Non-branching tree-decompositions
• Excluding a Forest Induced Minor
• Unavoidable pivot-minors in graphs of large rank-depth
• Finding minors in graphs with a given path structure
• On the structure of graphs with path-width at most two