| Abstrakt: |
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\'e [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\'nski 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'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. [ABSTRACT FROM AUTHOR] |
