Circumference and Pathwidth of Highly Connected Graphs

DOI10.1002/JGT.21825zbMATH Open1316.05076arXiv1309.7683OpenAlexW3123083091MaRDI QIDQ5265331FDOQ5265331

Emily A. Marshall, David R. Wood

Publication date: 23 July 2015

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

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.

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)

Cites Work

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

Cited In (3)

• Approximating Pathwidth for Graphs of Small Treewidth
• The edge-Erdős-Pósa property
• Directed width parameters and circumference of digraphs

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)