6-decomposition of snarks
type: Item
instance of: scholarly article
title: 6-decomposition of snarks
zbMATH Open document ID: 1256.05192
author: Ján Karabáš
author: E. Máčajová
author: Roman Nedela
published in: European Journal of Combinatorics
publication date: 2012-11-15T00:00:00Z
review text: \textit{R. Nedela} and \textit{M. Škoviera} proved in [J. Graph Theory 22, No. 3, 253--279 (1996; Zbl 0856.05082)] that when \(G\) is a snark with a \(k\)-edge cut, \(k\geq 2\), whose removal leaves two \(3\)-colorable components, then they can be both completed into snarks of order at most \(|G|\) by adding at most \(\kappa(k)\) vertices. The values of \(\kappa(k)\) are known for \(k=2,3,4,5\). The authors find a set of 14 complements that suffice to perform \(6\)-decompositions of snarks with at most 30 vertices. They also show that if this set is not complete to perform \(6\)-decompositions of all snarks, then \(\kappa(k) \geq 20\) and there are strong restrictions on the structure of the missing complements, if there are any.
reviewed by: Dalibor Fronček
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6106899
zbMATH Keywords: snarks
zbMATH Keywords: decomposition
zbMATH Keywords: complements
MaRDI profile type: Publication
full work available at URL: j.ejc.2012.07.019
OpenAlex ID: W2008317264
cites work: Snarks and reducibility
cites work: Decomposition of snarks
cites work: Factorisation of snarks
cites work: Construction of class two graphs with maximum vertex degree three
cites work: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
cites work: Decompositions and reductions of snarks
cites work: Classification and characterizations of snarks
cites work: Non-bicritical critical snarks
cites work: Q4529551
DOI: 10.1016/J.EJC.2012.07.019
description: scientific article; zbMATH DE number 6106899