Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.17789 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915872276217856 |
|---|---|
| author | Brinkmann, Gunnar Van Overberghe, Steven |
| author_facet | Brinkmann, Gunnar Van Overberghe, Steven |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17789 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algorithms for the Generation of Snarks Brinkmann, Gunnar Van Overberghe, Steven Combinatorics 05C15 05C85 05C30 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. |
| title | Algorithms for the Generation of Snarks |
| topic | Combinatorics 05C15 05C85 05C30 |
| url | https://arxiv.org/abs/2603.17789 |