Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth

Tony Huynh, Gwenaël Joret, Piotr Micek, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We prove a conjecture of Seymour (1993) stating that for every apex-forest H1 and out-erplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor. An independent proof was recently obtained by Dang and Thomas [3].

Original languageEnglish
Pages (from-to)839-868
Number of pages30
JournalCombinatorica
Volume40
DOIs
Publication statusPublished - 30 Nov 2020

Cite this