Paper
Algorithms for the Generation of Snarks
Authors
Gunnar Brinkmann, Steven Van Overberghe
Abstract
The essential requirement for a cubic graph to be called a snark is that it can not be edge-coloured with three colours. To avoid trivial cases, varying restrictions on the connectivity are imposed. Snarks are not only interesting in themselves, but also a valuable test field for conjectures about graphs that are not snarks and sometimes not even cubic. For many important open problems in graph theory it is proven that minimal counterexamples would be snarks. We give two new algorithms for the generation of snarks and results of computer programs implementing these algorithms. One algorithm is for snarks with girth exactly 4 and is used for generating complete lists of girth 4 snarks on up to 40 vertices. The second algorithm lists snarks with girth at least 5 and is used for generating complete lists of such snarks on up to 38 vertices. We also give complete lists of strong snarks (in the terminology of Jaeger) on up to 40 vertices.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2603.17789v1</id>\n <title>Algorithms for the Generation of Snarks</title>\n <updated>2026-03-18T14:50:28Z</updated>\n <link href='https://arxiv.org/abs/2603.17789v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2603.17789v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>The essential requirement for a cubic graph to be called a snark is that it can not be edge-coloured with three colours. To avoid trivial cases, varying\n restrictions on the connectivity are imposed. Snarks are not only interesting in themselves, but also a\n valuable test field for conjectures about graphs that are not snarks and sometimes not even cubic. For many important open problems in graph\n theory it is proven that minimal counterexamples would be snarks.\n We give two new algorithms for the generation of snarks and results of computer programs implementing these algorithms. One algorithm is for snarks with girth\n exactly 4 and is used for generating complete lists of girth 4 snarks on up to 40 vertices. The second algorithm lists snarks with girth at least 5 and is used\n for generating complete lists of such snarks on up to 38 vertices. We also give complete lists of strong snarks (in the terminology of Jaeger)\n on up to 40 vertices.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='math.CO'/>\n <published>2026-03-18T14:50:28Z</published>\n <arxiv:primary_category term='math.CO'/>\n <author>\n <name>Gunnar Brinkmann</name>\n </author>\n <author>\n <name>Steven Van Overberghe</name>\n </author>\n </entry>"
}