Cycle separating cuts in possible counterexamples to the cycle double cover and the Berge-Fulkerson conjectures
It is known that smallest counterexamples to Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture (if they exist) are cyclically 4- and 5-edge-connected, respectively. We further analyse small cycle separating cuts in possible counterexamples. We prove that if a smallest counterexample G to CDC Conjecture contains a cycle separating 4-cut S, then the behaviour of the admissible CDC coverings along the dangling edges of the two 4-poles induced by S is uniquely determined among more than 219 a priori possibilities. Similarly, for the Berge-Fulkerson Conjecture, we prove that among more than 2111 a priori possibilities, there are only 13 pairs of admissible sets that could occur along the dangling edges of a 5-cut in a smallest counterexample.
Authors
- Edita Máčajová (ORCID: https://orcid.org/0000-0001-5735-5513)
- Gloria Tabarelli
- Giuseppe Mazzuoccolo (ORCID: https://orcid.org/0000-0001-7775-065X)
Institutions
- University of Verona (IT)
- University of Modena and Reggio Emilia (IT)
- Comenius University Bratislava (SK)
Publication Details
- Journal
- Ars Mathematica Contemporanea
- Published
- 2025-03-11
- DOI
- https://doi.org/10.26493/1855-3974.3409.c13
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00