Pathwidth vs Cocircumference

.The circumference of a graph \(G\) with at least one cycle is the length of a longest cycle in \(G\). A classic result of Birmelé [J. Graph Theory, 43 (2003), pp. 24–25] 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ński et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659–664]). In this paper, we study whether similar bounds hold when replacing the circumference of \(G\) by its cocircumference, defined as the largest size of a bond in \(G\), an inclusionwise 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é'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.KeywordstreewidthpathwidthtreedepthcircumferencecocircumferenceMSC codes05C83