On the smallest snarks with oddness 4 and connectivity 2

MaRDI QIDQ1753089zbMATH OpenFDO

Authors Jan Goedgebeur

Publication date 25 May 2018

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

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

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

chromatic indexcomputationcubic graphexhaustive searchoddnesssnark

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A snark is a bridgeless cubic graph which is not 3-edge-colourable. The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph. Lukot'ka, M'acajov'a, Maz'ak and v{S}koviera showed in [Electron. J. Combin. 22 (2015)] that the smallest snark with oddness 4 has 28 vertices and remarked that there are exactly two such graphs of that order. However, this remark is incorrect as -- using an exhaustive computer search -- we show that there are in fact three snarks with oddness 4 on 28 vertices. In this note we present the missing snark and also determine all snarks with oddness 4 up to 34 vertices.

Review text

Summary: A \textit{snark} is a bridgeless cubic graph which is not 3-edge-colourable. The \textit{oddness} of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph. \textit{R. Lukoťka} et al. showed in [Electron. J. Comb. 22, No. 1, Research Paper P1.51, 20 p. (2015; Zbl 1308.05051)] that the smallest snark with oddness 4 has 28 vertices and remarked that there are exactly two such graphs of that order. However, this remark is incorrect as -- using an exhaustive computer search -- we show that there are in fact three snarks with oddness 4 on 28 vertices. In this note we present the missing snark and also determine all snarks with oddness 4 up to 34 vertices.

Recommendations

• The smallest nontrivial snarks of oddness 4
• Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
• Small snarks with large oddness
• Snarks with large oddness and small number of vertices
• Odd 2-factored snarks

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Generation and properties of snarks
• Generation of cubic graphs
• House of Graphs: a database of interesting graphs
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Polyhedral decompositions of cubic graphs
• Small snarks with large oddness

Cited in

(6)

• Small snarks with large oddness
• The smallest nontrivial snarks of oddness 4
• Odd 2-factored snarks
• scientific article; zbMATH DE number 1011074 (Why is no real title available?)
• Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
• Snarks with large oddness and small number of vertices

Describes a project that uses

Uses Software

• House of Graphs
• snarkhunter

This page was built for publication: On the smallest snarks with oddness 4 and connectivity 2

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