On snarks that are far from being 3-edge colorable

zbMATH Open1335.05064arXiv1203.2015MaRDI QIDQ281587FDOQ281587

Authors: Jonas Hägglund 

Publication date: 11 May 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Berge-Fulkerson conjecture on certain snarks
• Odd 2-factored snarks
• Berge-Fulkerson coloring for infinite families of snarks
• On Fulkerson conjecture

zbMATH Keywords

oddnessperfect matching coverssnarksuncolorability measures

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• Decompositions and reductions of snarks
• Classification and characterizations of snarks
• Double covers of cubic graphs with oddness 4
• Measurements of edge-uncolorability
• Five cycle double covers of some cubic graphs
• Snarks without small cycles
• Mácajová and Škoviera conjecture on cubic graphs
• The equivalence of two conjectures of Berge and Fulkerson
• Title not available (Why is that?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Generation and properties of snarks
• Polyhedral decompositions of cubic graphs
• Blocking and anti-blocking pairs of polyhedra
• On cycle-double covers of graphs of small oddness
• Three measures of edge-uncolorability

Cited In (28)

• Covering a cubic graph with perfect matchings
• Berge-Fulkerson coloring for infinite families of snarks
• On total coloring and equitable total coloring of infinite snark families
• Petersen cores and the oddness of cubic graphs
• On family of cubic graphs containing flower snarks
• Generation and properties of snarks
• On the strong circular 5‐flow conjecture
• A note on Fouquet-Vanherpes question and Fulkerson conjecture
• Families of dot-product snarks on orientable surfaces of low genus
• Odd 2-factored snarks
• Fulkerson's conjecture and Loupekine snarks
• Even cycle decompositions of index 3 by a novel coloring technique
• Some snarks are worse than others
• Uniquely edge-3-colorable graphs and snarks
• Measures of edge-uncolorability of cubic graphs
• Cubic graphs that cannot be covered with four perfect matchings
• Covering cubic graphs with matchings of large size
• Coverings of cubic graphs and 3-edge colorability
• Rotationally symmetric snarks from voltage graphs
• Quest for graphs of Frank number 3
• Title not available (Why is that?)
• Construction of permutation snarks
• The smallest nontrivial snarks of oddness 4
• Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
• Shortness coefficient of cyclically 4-edge-connected cubic graphs
• Roman domination and independent Roman domination on graphs with maximum degree three
• Treelike snarks
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark

This page was built for publication: On snarks that are far from being 3-edge colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281587)