On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings

DOI10.1002/jgt.21778zbMath1310.05089DBLPjournals/jgt/EsperetM14arXiv1301.6926OpenAlexW3126075510WikidataQ56001761 ScholiaQ56001761MaRDI QIDQ2922223

Louis Esperet, Giuseppe Mazzuoccolo

Publication date: 9 October 2014

Published in: Journal of Graph Theory, The Seventh European Conference on Combinatorics, Graph Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.6926

zbMATH Keywords

cubic graphsperfect matchingssnarksBerge-Fulkerson conjectureshortest cycle coversnarks.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings ⋮ Covering a cubic graph by 5 perfect matchings ⋮ Covering a cubic graph with perfect matchings ⋮ Ban–Linial's Conjecture and treelike snarks ⋮ Petersen Cores and the Oddness of Cubic Graphs ⋮ On total coloring and equitable total coloring of infinite snark families ⋮ Deciding whether four perfect matchings can cover the edges of a snark is NP-complete ⋮ Some snarks are worse than others ⋮ Rotationally symmetric snarks from voltage graphs ⋮ Perfect matching covers of cubic graphs of oddness 2 ⋮ An equivalent formulation of the Fan-Raspaud Conjecture and related problems ⋮ Berge-Fulkerson coloring for infinite families of snarks ⋮ Measures of edge-uncolorability of cubic graphs ⋮ Cubic Graphs with No Short Cycle Covers ⋮ Treelike snarks ⋮ Cubic graphs that cannot be covered with four perfect matchings ⋮ S_12 and P_12-colorings of cubic graphs ⋮ Perfect Matching Index versus Circular Flow Number of a Cubic Graph ⋮ On the maximum fraction of edges covered by \(t\) perfect matchings in a cubic bridgeless graph ⋮ A class of cubic graphs satisfying Berge conjecture

Cites Work

• Unnamed Item
• On snarks that are far from being 3-edge colorable
• Generation and properties of snarks
• Shortest coverings of graphs with cycles
• Short cycle covers and the cycle double cover conjecture
• Shortest circuit covers of cubic graphs
• On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings
• Short Cycle Covers of Graphs with Minimum Degree Three
• The equivalence of two conjectures of Berge and Fulkerson
• Covering Multigraphs by Simple Circuits
• The NP-Completeness of Edge-Coloring
• Short cycle covers of cubic graphs
• Polyhedral decompositions of cubic graphs
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings