Back to Search
Start Over
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
- Source :
- Journal of Combinatorial Theory, Series B. 160:1-14
- Publication Year :
- 2023
- Publisher :
- Elsevier BV, 2023.
-
Abstract
- Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$. It can be shown that given an arbitrary perfect matching of $G$, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$-factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$, there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$, there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection.<br />13 pages, 8 figures
Details
- ISSN :
- 00958956
- Volume :
- 160
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Theory, Series B
- Accession number :
- edsair.doi.dedup.....da5b3b41a28bf140eb9998a63b094984
- Full Text :
- https://doi.org/10.1016/j.jctb.2022.12.003