<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
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é (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ński, 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é'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.
v2: revised following the referees' comments
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |