Circumference and pathwidth of highly connected graphs

Emily A Marshall, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most inline image. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele s theorem was extended by Birmele et al. [Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth inline image. Our main result states that, under the additional assumption of inline image-connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth inline image. Moreover, examples show that inline image-connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k-connected H-minor-free graph have bounded pathwidth? We discuss this question and provide a few observations.
Original languageEnglish
Pages (from-to)222 - 232
Number of pages11
JournalJournal of Graph Theory
Volume79
Issue number3
DOIs
Publication statusPublished - 2015

Cite this