Home > Search Results: Rollová, Edita
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
Matching covers of cubic graphs
 Slívová, Veronika ; Šámal, Robert (advisor) ; Rollová, Edita (referee)
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.
Detailed record
Variants of Petersen coloring for some graph classes
 Bílková, Hana ; Šámal, Robert (advisor) ; Rollová, Edita (referee)
Normal coloring - an equivalent version of Petersen coloring - is a special proper 5-edge-coloring of cubic graphs. Every edge in a normally colored graph is normal, i.e. it uses together with its four neighbours either only three colors or all five colors. Jaeger conjectured that every bridgeless cubic graph has a normal coloring. This conjecture, if true, imply for example Cycle double cover conjecture. Here we solve a weakened version of Jaeger's problem. We are looking for a proper 5-edge-coloring such that at least a part of the edges is normal. We show a coloring of generalized prisms with two thirds of the edges normal and a coloring of graphs without short cycles with almost half of the edges normal. Then we propose a new approach to normal coloring - chains. We use chains to prove that there cannot be only one single mistake in an almost normally colored graph. We also prove some statements about cuts in a normally colored graph which also follow from nowhere-zero Petersen flow. Finally, we examine a four-cycle in a normally colored graph. 1
Detailed record

See also: similar author names
1 Rollová, Elisabeth
Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English