Berge–Fulkerson Conjecture, Perfect Matching Partial Coverings and Odd Dividers
Journal of Graph Theory · 14.07.2026
DOI: 10.1002/jgt.70097 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 14.07.2026. Verfasst von Yilun Luo und 4 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben.
Abstract (Originalsprache)
It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them. The Fan‐Raspaud conjecture, implied by the Berge‐Fulkerson conjecture, holds for all graphs of oddness two due to Máčajová and Škoviera (Combinatorica [2014]). An interesting problem is to investigate the validity of the Berge‐Fulkerson conjecture for graphs of oddness two, especially permutation graphs. In this study, we propose a new approach to the Berge–Fulkerson conjecture by finding a relationship between the conjecture and perfect matching partial coverings. As applications of the main results, the conjecture is confirmed for permutation graphs containing an ‐alternating circuit of length at most 16, which improves early results about ‐alternating circuits of length 8 and 12.
Zitieren
APA
Luo, Y., Hao, R., Luo, R., Zhang, C., & Zhou, W. (2026). Berge–Fulkerson Conjecture, Perfect Matching Partial Coverings and Odd Dividers. Journal of Graph Theory. https://doi.org/10.1002/jgt.70097
Vancouver
Luo Y, Hao R, Luo R, Zhang C, Zhou W. Berge–Fulkerson Conjecture, Perfect Matching Partial Coverings and Odd Dividers. Journal of Graph Theory. 2026. doi:10.1002/jgt.70097
BibTeX
@article{Luo2026,
author = {Luo, Yilun and Hao, Rong‐Xia and Luo, Rong and Zhang, Cun‐Quan and Zhou, Wenjuan},
title = {Berge–Fulkerson Conjecture, Perfect Matching Partial Coverings and Odd Dividers},
journal = {Journal of Graph Theory},
year = {2026},
doi = {10.1002/jgt.70097}
}
EUVIMED