Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44

DOI10.26493/1855-3974.1601.E75zbMATH Open1416.05104arXiv1712.07867OpenAlexW3105907074MaRDI QIDQ5225040FDOQ5225040

Authors: Jan Goedgebeur, E. Máčajová, Martin Škoviera 

Publication date: 25 July 2019

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

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.

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

Recommendations

• The smallest nontrivial snarks of oddness 4
• On the smallest snarks with oddness 4 and connectivity 2
• Small snarks with large oddness
• Snarks with large oddness and small number of vertices
• Snarks without small cycles

zbMATH Keywords

computationcubic graphoddnesssnarkedge-colouringcyclic connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21) Enumeration in graph theory (05C30) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Cites Work

• House of Graphs: a database of interesting graphs
• Practical graph isomorphism. II.
• The Generation of Fullerenes
• The NP-Completeness of Edge-Coloring
• The hunting of a snark with total chromatic number 5
• On the total coloring of certain graphs
• Title not available (Why is that?)
• Decompositions and reductions of snarks
• Title not available (Why is that?)
• 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
• On snarks that are far from being 3-edge colorable
• Hamiltonian results inK1,3-free graphs
• Title not available (Why is that?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Generation and properties of snarks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Colour Numbers of Complete Graphs
• A Theorem on Coloring the Lines of a Network
• Special classes of snarks
• Almost all cubic graphs are Hamiltonian
• Title not available (Why is that?)
• Sparsely intersecting perfect matchings in cubic graphs
• Minimal Cyclic-4-Connected Graphs
• Title not available (Why is that?)
• Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks
• A note about the dominating circuit conjecture
• Title not available (Why is that?)
• Snarks with large oddness and small number of vertices
• Removable edges in cyclically 4-edge-connected cubic graphs
• Superposition and constructions of graphs without nowhere-zero \(k\)-flows
• Graphes Cubiques D'Indice Chromatique Quatre
• Measures of edge-uncolorability of cubic graphs
• Factorisation of snarks
• Irreducible snarks of given order and cyclic connectivity
• Decomposition of snarks
• A Proof of 4-Coloring the Edges of a Cubic Graph
• Network-Colourings
• Title not available (Why is that?)
• On the smallest snarks with oddness 4 and connectivity 2
• The smallest nontrivial snarks of oddness 4

Cited In (5)

• Morphology of small snarks
• Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs
• Irreducible snarks of given order and cyclic connectivity
• Decomposition of cubic graphs with cyclic connectivity 5
• The smallest nontrivial snarks of oddness 4

Uses Software

• nauty
• House of Graphs
• Traces
• snarkhunter

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)