Circumference and pathwidth of highly connected graphs

DOI10.1002/JGT.21825MaRDI QIDQ5265331zbMATH OpenOpenAlexFDO

Authors Emily A. Marshall, David R. Wood

Publication date 23 July 2015

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7683

zbMATH Keywords

pathwidthhighly connectedminor-free

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40)

Abstract: Birmele [J. Graph Theory, 2003] proved that every graph with circumference t has treewidth at most t-1. Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger result. Birmele's theorem was extended by Birmele, Bondy and Reed [Combinatorica, 2007] who showed that every graph without k disjoint cycles of length at least t has bounded treewidth (as a function of k and t). Our main result states that, under the additional assumption of (k + 1)- connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth O(t^3 + tk^2). Moreover, examples show that (k + 1)-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.

Recommendations

• On 3-connected graphs of path-width at most three
• Seymour's conjecture on 2-connected graphs of large pathwidth
• Connected tree-width
• Bounding connected tree-width
• The circumference of a graph with no \(K_{3,t}\)-minor

Cites work

• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A tighter Erdős-Pósa function for long cycles
• An extremal function for contractions of graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximation of pathwidth of outerplanar graphs
• Graph minors. III. Planar tree-width
• Homomorphiesätze für Graphen
• Lower bound of the Hadwiger number of graphs by their average degree
• Quickly excluding a forest
• Some Theorems on Abstract Graphs
• Sparsity. Graphs, structures, and algorithms
• The Erdős-Pósa property for long circuits
• Tree-width and circumference of graphs

Cited in

(7)

• The edge-Erdős-Pósa property
• Approximating Pathwidth for Graphs of Small Treewidth
• On 3-connected graphs of path-width at most three
• Directed width parameters and circumference of digraphs
• Pathwidth vs Cocircumference
• Treedepth vs circumference
• Seymour's conjecture on 2-connected graphs of large pathwidth

This page was built for publication: Circumference and pathwidth of highly connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265331)