Pathwidth vs Cocircumference

DOI10.1137/23M158663XMaRDI QIDQ6195950zbMATH OpenFDO

Authors Marcin Briański, Gwenaël Joret, Michał T. Seweryn

Publication date 14 March 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circumferencecocircumferencepathwidthtreedepthtreewidth

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: The {em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper bound also holds for the pathwidth of $G$; in fact, even the treedepth of $G$ is upper bounded by its circumference (Bria'nski, Joret, Majewski, Micek, Seweryn, Sharma; 2023). In this paper, we study whether similar bounds hold when replacing the circumference of $G$ by its {em cocircumference}, defined as the largest size of a {em bond} in $G$, an inclusion-wise minimal set of edges $F$ such that $G-F$ has more components than $G$. In matroidal terms, the cocircumference of $G$ is the circumference of the bond matroid of $G$. Our first result is the following `dual' version of Birmel'e's theorem: The treewidth of a graph $G$ is at most its cocircumference. Our second and main result is an upper bound of $3k-2$ on the pathwidth of a $2$-connected graph $G$ with cocircumference $k$. Contrary to circumference, no such bound holds for the treedepth of $G$. Our two upper bounds are best possible up to a constant factor.

Recommendations

• Treedepth vs circumference
• Circumference and pathwidth of highly connected graphs
• Extremal graphs with prescribed circumference and cocircumference
• Circumference and girth
• scientific article; zbMATH DE number 147640

Cites work

• Approximation of pathwidth of outerplanar graphs
• Branchwidth of graphic matroids
• First order convergence of matroids
• Graph minors. X: Obstructions to tree-decomposition
• Matroid Pathwidth and Code Trellis Complexity
• New spectral lower bounds on the bisection width of graphs
• On infinite antichains of matroids
• On Rota's conjecture and excluded minors containing large projective geometries.
• Tree-width and circumference of graphs
• Treedepth vs circumference

Cited in

(1)

• Treedepth vs circumference

This page was built for publication: Pathwidth vs Cocircumference

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