PreprintarXiv licencearXiv
Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
Abstract
The Berge conjecture [Proc. London Math. Soc., 1979] asserts that every bridgeless cubic graph can be covered by five perfect matchings. The 5-cycle double cover conjecture, proposed independently by Preissmann (1981) and Celmins (1984), asserts that every bridgeless graph admits five even subgraphs such that every edge belongs to exactly two of them. Hakobyan and Mkrtchyan [Ars Math. Contemp., 2019] proved that the 5-cycle double cover conjecture holds if and only if every bridgeless claw-free cubic graph can be covered by four perfect matchings. In this paper, we prove that the Berge conjecture holds for every bridgeless claw-free cubic graph G and that G has four perfect matchings covering at least 299/315|E(G)| edges.
Related
- A tris of perfect matchings in bridgeless claw-free cubic graphs
- Exact local spectral thresholds for perfect matchings in $3$-graphs and $3$-partite $3$-graphs
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
- Perfect matchings in planar 3-connected graphs: girth five and minimum degree five
- Hamilton paths and cycles in flip graphs of (almost-)perfect matchings
BibTeX
@misc{zhou2026covering,
title = {{Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings}},
author = {Huaibin Zhou and Xiumei Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01137},
eprint = {2610.01137},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01137},
}
RIS
TY - UNPB
TI - Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
AU - Huaibin Zhou
AU - Xiumei Wang
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.01137
UR - https://arxiv.org/abs/2610.01137
AB - The Berge conjecture [Proc. London Math. Soc., 1979] asserts that every bridgeless cubic graph can be covered by five perfect matchings. The 5-cycle double cover conjecture, proposed independently by Preissmann (1981) and Celmins (1984), asserts that every bridgeless graph admits five even subgraphs such that every edge belongs to exactly two of them. Hakobyan and Mkrtchyan [Ars Math. Contemp., 2019] proved that the 5-cycle double cover conjecture holds if and only if every bridgeless claw-free cubic graph can be covered by four perfect matchings. In this paper, we prove that the Berge conjecture holds for every bridgeless claw-free cubic graph G and that G has four perfect matchings covering at least 299/315|E(G)| edges.
ER -