Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth
Copyright policy )Seymour’s Conjecture on 2-Connected Graphs of Large Pathwidth
We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas.
v4: Small changes suggested by a referee
- Monash University Australia
- Université Libre de Bruxelles Belgium
- Jagiellonian University Poland
- Sapienza University of Rome Italy
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Théorie des graphes, Mathematics - Combinatorics, Combinatorics (math.CO), graphs, pathwidth, connectivity, outerplanar graphs, trees, 05C83, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Théorie des graphes, Mathematics - Combinatorics, Combinatorics (math.CO), graphs, pathwidth, connectivity, outerplanar graphs, trees, 05C83, Computer Science - Discrete Mathematics
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!