Deciding whether four perfect matchings can cover the edges of a snark is NP-complete

DOI10.1016/j.tcs.2023.114374MaRDI QIDQ6150678

Peter Varša, Martin Škoviera

Publication date: 9 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-completenesscubic graphsnarkperfect matchingedge colouring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generation and properties of snarks
• Treelike snarks
• Snarks without small cycles
• Cubic graphs that cannot be covered with four perfect matchings
• Superposition of snarks revisited
• Projective, affine, and abelian colorings of cubic graphs
• On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings
• The NP-Completeness of Edge-Coloring
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• 1‐Factor and Cycle Covers of Cubic Graphs
• Perfect Matching Index versus Circular Flow Number of a Cubic Graph
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: Deciding whether four perfect matchings can cover the edges of a snark is NP-complete