Abstract
The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strongly related to a famous conjecture of Berge and Fulkerson. In this paper we show that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. Our proof makes heavy use of small cuts, so an interesting problem is to construct large snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. A well-known example is the Petersen graph and the unique other known examples were recently found by Hägglund using a computer program. In this paper we construct an infinite family F of snarks whose edge-set cannot be covered by 4 perfect matchings. It turns out that the family F also has interesting properties with respect to the shortest cycle cover problem. The Petersen graph and one of the graphs constructed by Hägglund are the only known snarks with m edges and no cycle cover of length 4/3m (indeed their shortest cycle covers have length 4/3m + 1). We show that all the members of F satisfy the former property, and we construct a snark with no cycle cover of length less than 4/3m+ 2.
Partially supported by the French Agence Nationale de la Recherche under reference ANR-10-JCJC-0204-01.
Research supported by a fellowship from the European Project “INdAM fellowships in mathematics and/or applications for experienced researchers cofunded by Marie Curie actions”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon and M. Tarsi, Covering multigraphs by simple circuits, SIAM J. Algebraic Discrete Methods 6 (1985), 345–350.
A. Bonisoli and D. Cariolaro, Excessive Factorizations of Regular Graphs, In: Graph theory in Paris, A. Bondy et al. (eds.), Birkhäuser, Basel (2007), 73–84.
G. Brinkmann, J. Goedgebeur, J. Hägglund and K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B, to appear.
L. Esperet and G. Mazzuoccolo, On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings, Manuscript, 2013. arXiv:1301.6926
J. L. Fouquet and J. M. Vanherpe, On the perfect matching index of bridgeless cubic graphs, Manuscript, 2009. arXiv:0904.1296.
D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168–194.
J. Hägglund, On snarks that are far from being 3-edge colorable, Manuscript, 2012. arXiv:1203.2015
X. Hou, H. J. Lai and C. Q. Zhang, On matching coverings and cycle coverings, Manuscript, 2012.
T. Kaiser, D. Král’, B. Lidický, P. Nejedlý and R. Šámal, Short cycle covers of cubic graphs and graphs with minimum degree three, SIAM J. Discrete Math. 24 (2010), 330–355.
G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory 68 (2011) 125–128.
E. Steffen, 1-factor and cycle covers of cubic graphs, Manuscript, 2012. arXiv:1209.4510
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2013 Scuola Normale Superiore Pisa
About this paper
Cite this paper
Esperet, L., Mazzuoccolo, G. (2013). On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings. In: Nešetřil, J., Pellegrini, M. (eds) The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series, vol 16. Edizioni della Normale, Pisa. https://doi.org/10.1007/978-88-7642-475-5_8
Download citation
DOI: https://doi.org/10.1007/978-88-7642-475-5_8
Publisher Name: Edizioni della Normale, Pisa
Print ISBN: 978-88-7642-474-8
Online ISBN: 978-88-7642-475-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)