Snarks without small cycles
From MaRDI portal
Snarks are non-trivial (i.e., cyclically 4-edge-connected) 3-regular graphs whose edges cannot be colored with three colors. Jaeger and Swart conjectured that any snark has girth (the length of the shortest cycle) at most 6. This problem is also known as the girth conjecture of snarks. The aim of this paper is to give a negative solution of this conjecture and to construct snarks with arbitrarily large girths. For instance, using known constructions of cubic graphs with large girths, we can explicitly construct cyclically 5-edge-connected snarks of order \(n\) and with girth at least \(({4\over 3}\pm o(1))\log_2 n\), what is an asymptotically optimal result.
Recommendations
Cited in
(65)- A cyclically 6-edge-connected snark of order 118
- Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks.
- Classification and characterizations of snarks
- Uniquely edge-3-colorable graphs and snarks
- Superposition and constructions of graphs without nowhere-zero k-flows
- Measurements of edge-uncolorability
- A revival of the girth conjecture
- Reducible configurations for the cycle double cover conjecture
- Berge-Fulkerson coloring for some families of superposition snarks
- Girth, oddness, and colouring defect of snarks
- Coverings of cubic graphs and 3-edge colorability
- Superposition of snarks revisited
- Some results on the structure of multipoles in the study of snarks
- Small snarks with large oddness
- Snarks from a Kászonyi perspective: a survey
- Odd 2-factored snarks
- Fulkerson's conjecture and Loupekine snarks
- Cycle double covers and spanning minors. I
- Irreducible snarks of given order and cyclic connectivity
- Forbidden triples generating a finite set of 3-connected graphs
- On snarks that are far from being 3-edge colorable
- The Fan-Raspaud conjecture: a randomized algorithmic approach and application to the pair assignment problem in cubic networks
- Cubic graphs with large circumference deficit
- scientific article; zbMATH DE number 3884206 (Why is no real title available?)
- Hypohamiltonian Snarks with Cyclic Connectivity 5 and 6
- Circular chromatic index of type 1 Blanuša snarks
- 3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
- Polyhedral embeddings of snarks in orientable surfaces
- On generating snarks
- Circuits of length 5 in 2-factors of cubic graphs
- On stable cycles and cycle double covers of graphs with large circumference
- Generation and properties of snarks
- 1-factor and cycle covers of cubic graphs
- Between Proper and Strong Edge-Colorings of Subcubic Graphs
- Induced embeddings into Hamming graphs
- AVD-total-chromatic number of some families of graphs with \(\Delta(G) = 3\)
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- Cubic Cayley graphs and snarks
- Generation of cubic graphs and snarks with large girth
- On the number of colorings of a snark minus an edge
- Circuit double covers of graphs
- 5-Cycle Double Covers, 4-Flows, and Catlin Reduction
- Circular edge-colorings of cubic graphs with girth six
- Circular edge-colorings of cubic graphs with girth six
- On the maximum number of edges in chordal graphs of bounded degree and matching number
- Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms
- Between proper and strong edge‐colorings of subcubic graphs
- Roman domination and independent Roman domination on graphs with maximum degree three
- Cubic graphs with colouring defect 3
- On total coloring and equitable total coloring of infinite snark families
- Flow resistance to resistance ratios in cubic graphs
- Deciding whether four perfect matchings can cover the edges of a snark is NP-complete
- Infinitely many hypohamiltonian cubic graphs of girth 7
- Normal 5-edge-coloring of some snarks superpositioned by flower snarks
- Measures of edge-uncolorability of cubic graphs
- Regular colouring defect of a cubic graph and the conjectures of Fan-Raspaud and Fulkerson
- Stars in forbidden triples generating a finite set of 4-connected graphs
- Resistance, oddness and colouring defect of snarks
- 4-coverable snarks, perfect matching cover, and Isaacs product
- Non-conflicting no-where zero Z₂ Z₂-flows in cubic graphs
- Treelike snarks
- Forbidden triples containing a complete graph and a complete bipartite graph of small order
- Infinite classes of dihedral snarks
- The circular chromatic index of graphs of high girth
- Smallest counterexample to the 5-flow conjecture has girth at least eleven
This page was built for publication: Snarks without small cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924136)
