pith. sign in

arxiv: 1712.04549 · v2 · pith:5JKBE653new · submitted 2017-12-12 · 🧮 math.CO · cs.DM

Minors of two-connected graphs of large path-width

classification 🧮 math.CO cs.DM
keywords graphpath-widthanswersbackslashconjectureconnectedeveryexists
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An Overview of Universal Obstructions for Graph Parameters

    cs.DM 2023-04 unverdicted novelty 3.0

    The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.