Original title:
Pokrývání kubických grafů párováními
Translated title:
Matching covers of cubic graphs
Authors:
Slívová, Veronika ; Šámal, Robert (advisor) ; Rollová, Edita (referee) Document type: Master’s theses
Year:
2017
Language:
eng Abstract:
[eng][cze] 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.Hypotéza Berge a Fulkersona říká, že každý kubický graf bez mostů lze pokrýt šesti perfektními párováními tak, aby každá hrana byla obsažena právě ve dvou z nich. Další hypotéza od Berge říká, že každý kubický graf bez mostů lze pokrýt pomocí pěti perfektních párování. Obě hypotézy jsou zkoumány přes čtyřicet let. Abreu a kol. [2016] vytvořili novou třídu kubických grafů, zvanou treelike snarky a ukázali, že grafy z této třídy nemohou být pokryty méně než pěti perfektními párováními. My ukážeme, že jejich dolní odhad na počet perfektních párování je těsný. Bergovu domněnku dokonce dokážeme pro větší třídu grafů. Nakonec ukážeme, že také Berge-Fulkersonova hypotéza platí pro třídu treelike snarků.
Keywords:
Berge-Fulkerson conjecture; cubic graphs; perfect matching; treelike snarks; Berge-Fulkersonova hypotéza; kubické grafy; perfektní párování; treelike snarky
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/85651