Circumference and Pathwidth of Highly Connected Graphs
Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . 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 etal. [Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth . Our main result states that, under the additional assumption of -connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that -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.
pathwidth highly connected minor-free