On snarks that are far from being 3-edge colorable

MaRDI QIDQ281587zbMATH OpenFDO

Authors Jonas Hägglund

Publication date 11 May 2016

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

Full work available at URL https://arxiv.org/abs/1203.2015, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p6

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• Blocking and anti-blocking pairs of polyhedra
• Classification and characterizations of snarks
• Decompositions and reductions of snarks
• Double covers of cubic graphs with oddness 4
• Five cycle double covers of some cubic graphs
• Generation and properties of snarks
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Measurements of edge-uncolorability
• Mácajová and Škoviera conjecture on cubic graphs
• On cycle-double covers of graphs of small oddness
• Polyhedral decompositions of cubic graphs
• Snarks without small cycles
• The equivalence of two conjectures of Berge and Fulkerson
• 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
• Families of dot-product snarks on orientable surfaces of low genus
• A note on Fouquet-Vanherpes question and Fulkerson conjecture
• On the strong circular 5‐flow conjecture
• Odd 2-factored snarks
• Fulkerson's conjecture and Loupekine snarks
• Even cycle decompositions of index 3 by a novel coloring technique
• Uniquely edge-3-colorable graphs and snarks
• Some snarks are worse than others
• 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
• Construction of permutation snarks
• scientific article; zbMATH DE number 6965186 (Why is no real title available?)
• 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
• Treelike snarks
• Roman domination and independent Roman domination on graphs with maximum degree three
• 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)