Permutation snarks with order congruent to six modulo eight
A cycle permutation graph is a finite simple cubic graph with a 2-factor consisting of two chordless cycles; equivalently, it consists of two disjoint $k$-cycles, for some $k \ge 3$, and a perfect matching between their vertex sets. A permutation snark is a cycle permutation graph that is not 3-edge-colourable. If $k$ is even, the two cycles and the matching give a 3-edge-colouring, so every permutation snark has order $2$ or $6$ modulo $8$. Brinkmann, Goedgebeur, Hägglund and Markström found that every permutation snark on at most $36$ vertices has order $2$ modulo $8$. Máčajová and Škoviera constructed permutation snarks of every order $n \equiv 2 \pmod 8$ with $n \ge 10$, and showed that a smallest permutation snark of order $6$ modulo $8$, if one exists, is cyclically 5-edge-connected. Goedgebeur, Renders and Van Overberghe showed by exhaustive generation that it has at least $54$ vertices.
Problem. Is there a permutation snark $G$ with $|V(G)| \equiv 6 \pmod 8$, that is, one whose two cycles have length $k \equiv 3 \pmod 4$? Equivalently, is some cycle permutation graph of such an order not 3-edge-colourable? No condition on girth or connectivity is imposed.
Source: Brinkmann, Goedgebeur, Hägglund and Markström (2013), Problem 1, as whether every permutation snark has order 2 modulo 8; see Máčajová and Škoviera (2019), Section 4.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, cubic graphs, edge colorings, snarks
References
@article{brinkmann2013,
author = {Brinkmann, Gunnar and Goedgebeur, Jan and H{\"a}gglund, Jonas and Markstr{\"o}m, Klas},
title = {Generation and properties of snarks},
journal = {J. Combin. Theory Ser. B},
volume = {103},
number = {4},
year = {2013},
pages = {468--488},
doi = {10.1016/j.jctb.2013.05.001},
eprint = {1206.6690},
archivePrefix = {arXiv},
}
@article{macajova2019,
author = {M{\'a}{\v{c}}ajov{\'a}, Edita and {\v{S}}koviera, Martin},
title = {Permutation snarks of order 2 (mod 8)},
journal = {Acta Math. Univ. Comenian. (N.S.)},
volume = {88},
number = {3},
year = {2019},
pages = {929--934},
url = {https://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1313},
}
@article{goedgebeur2026,
author = {Goedgebeur, Jan and Renders, Jarne and Van Overberghe, Steven},
title = {Generation of cycle permutation graphs and permutation snarks},
journal = {Math. Comp.},
year = {2026},
doi = {10.1090/mcom/4247},
eprint = {2411.12606},
archivePrefix = {arXiv},
note = {Published electronically 13 August 2026},
}
@misc{aim-permutation-snark-order-residue,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Permutation snarks with order congruent to six modulo eight}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/620-permutation-snark-order-residue.md},
note = {Entry 620 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00371, "Permutation snarks with order congruent to six modulo eight", clopen.solutions.