Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
From MaRDI portal
Publication:5225040
Abstract: The family of snarks -- connected bridgeless cubic graphs that cannot be 3-edge-coloured -- is well-known as a potential source of counterexamples to several important and long-standing conjectures in graph theory. These include the cycle double cover conjecture, Tutte's 5-flow conjecture, Fulkerson's conjecture, and several others. One way of approaching these conjectures is through the study of structural properties of snarks and construction of small examples with given properties. In this paper we deal with the problem of determining the smallest order of a nontrivial snark (that is, one which is cyclically 4-edge-connected and has girth at least 5) of oddness at least 4. Using a combination of structural analysis with extensive computations we prove that the smallest order of a snark with oddness at least 4 and cyclic connectivity 4 is 44. Formerly it was known that such a snark must have at least 38 vertices [J. Combin. Theory Ser. B 103 (2013), 468--488] and one such snark on 44 vertices was constructed by Lukot'ka et al. [Electron. J. Combin. 22 (2015), #P1.51]. The proof requires determining all cyclically 4-edge-connected snarks on 36 vertices, which extends the previously compiled list of all such snarks up to 34 vertices [J. Combin. Theory Ser. B, loc. cit.]. As a by-product, we use this new list to test the validity of several conjectures where snarks can be smallest counterexamples.
Recommendations
Cites work
- scientific article; zbMATH DE number 3643299 (Why is no real title available?)
- scientific article; zbMATH DE number 3885954 (Why is no real title available?)
- scientific article; zbMATH DE number 3937197 (Why is no real title available?)
- scientific article; zbMATH DE number 4075098 (Why is no real title available?)
- scientific article; zbMATH DE number 3600073 (Why is no real title available?)
- scientific article; zbMATH DE number 867711 (Why is no real title available?)
- scientific article; zbMATH DE number 874369 (Why is no real title available?)
- scientific article; zbMATH DE number 3895104 (Why is no real title available?)
- scientific article; zbMATH DE number 6472882 (Why is no real title available?)
- scientific article; zbMATH DE number 3102311 (Why is no real title available?)
- A Proof of 4-Coloring the Edges of a Cubic Graph
- A Theorem on Coloring the Lines of a Network
- A note about the dominating circuit conjecture
- Almost all cubic graphs are Hamiltonian
- Classification and characterizations of snarks
- Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks
- Decomposition of snarks
- Decompositions and reductions of snarks
- Double covers of cubic graphs with oddness 4
- Factorisation of snarks
- Five cycle double covers of some cubic graphs
- Generation and properties of snarks
- Generation of cubic graphs
- Graphes Cubiques D'Indice Chromatique Quatre
- Hamiltonian results inK1,3-free graphs
- House of Graphs: a database of interesting graphs
- Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
- Irreducible snarks of given order and cyclic connectivity
- Measurements of edge-uncolorability
- Measures of edge-uncolorability of cubic graphs
- Minimal Cyclic-4-Connected Graphs
- Network-Colourings
- On snarks that are far from being 3-edge colorable
- On the smallest snarks with oddness 4 and connectivity 2
- On the total coloring of certain graphs
- Practical graph isomorphism. II.
- Removable edges in cyclically 4-edge-connected cubic graphs
- Snarks with large oddness and small number of vertices
- Sparsely intersecting perfect matchings in cubic graphs
- Special classes of snarks
- Superposition and constructions of graphs without nowhere-zero \(k\)-flows
- The Colour Numbers of Complete Graphs
- The NP-Completeness of Edge-Coloring
- The hunting of a snark with total chromatic number 5
- The smallest nontrivial snarks of oddness 4
Cited in
(9)- Permutation snarks of order \(2 \pmod{8}\)
- The smallest nontrivial snarks of oddness 4
- Snarks with large oddness and small number of vertices
- Morphology of small snarks
- Small snarks with large oddness
- Irreducible snarks of given order and cyclic connectivity
- Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs
- On the smallest snarks with oddness 4 and connectivity 2
- Decomposition of cubic graphs with cyclic connectivity 5
This page was built for publication: Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5225040)
