Permutation snarks without five-cycles
A cycle permutation graph is a finite simple cubic graph consisting of two disjoint cycles of equal length together with a perfect matching between their vertex sets; equivalently, a cubic graph with a 2-factor consisting of two chordless cycles. A permutation snark is a cycle permutation graph with no proper 3-edge-colouring; the Petersen graph is one. Every permutation snark has girth at least 5, and Shawe-Taylor and Pisanski constructed cycle permutation graphs of arbitrarily large girth. Goedgebeur, Renders and Van Overberghe showed by exhaustive computer search that a permutation snark of girth at least 6 has at least 50 vertices.
Problem. Is there a permutation snark of girth at least 6? Equivalently, does some cycle permutation graph of girth at least 6 have no proper 3-edge-colouring? One example suffices; its order is not prescribed.
Source: Stated by AIM — Open Applied Problems, after Goedgebeur, Renders and Van Overberghe (2026), Section 3 and Proposition 5, and Máčajová and Škoviera (2019), Section 4.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, cycle permutation graphs, edge colourings, snarks
References
@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},
}
@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{shawetaylor1982,
author = {Shawe-Taylor, J. and Pisanski, T.},
title = {Cycle permutation graphs with large girth},
journal = {Glas. Mat. Ser. III},
volume = {17(37)},
number = {2},
year = {1982},
pages = {233--236},
}
@misc{aim-permutation-snark-large-girth,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Permutation snarks without five-cycles}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/621-permutation-snark-large-girth.md},
note = {Entry 621 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-00370, "Permutation snarks without five-cycles", clopen.solutions.