Return to search

Pokrývání kubických grafů párováními / Matching covers of cubic graphs

Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:355996
Date January 2017
CreatorsSlívová, Veronika
ContributorsŠámal, Robert, Rollová, Edita
Source SetsCzech ETDs
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0018 seconds