Removable cycles in cycle permutation graphs
A cycle permutation graph is a finite simple cubic graph with a 2-factor consisting of two chordless cycles; such a 2-factor is a permutation 2-factor. For a permutation 2-factor $F$ of $G$, a cycle $C$ of $G$ is removable relative to $F$ if the spanning subgraph $$G - \bigl(E(C) \cap E(F)\bigr),$$ obtained by deleting only the edges of $C$ that lie in $F$, is 2-connected. The Petersen graph has no cycle removable relative to any of its permutation 2-factors. Goddyn, van den Heuvel and McGuinness note that the assertion below holds for 3-edge-colourable cycle permutation graphs and for cycle permutation graphs without a Petersen minor. Brinkmann, Goedgebeur, Hägglund and Markström, and then Goedgebeur, Renders and Van Overberghe, found by computer that the Petersen graph is the only permutation snark (cycle permutation graph with no proper 3-edge-colouring) on at most 36, and then at most 48, vertices without removable cycles.
Problem. Does every cycle permutation graph $G$ not isomorphic to the Petersen graph have a permutation 2-factor $F$ and a cycle $C$ removable relative to $F$? Both $F$ and $C$ may be chosen; the conclusion is not required for every permutation 2-factor of $G$.
Source: Goddyn, in Goddyn, van den Heuvel and McGuinness (1997); in this form, Goedgebeur, Renders and Van Overberghe (2026), Conjecture 3.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Keywords
- AIM Open Applied Problems, cycle permutation graphs, removable cycles, snarks
References
@article{goddyn1997,
author = {Goddyn, Luis A. and van den Heuvel, Jan and McGuinness, Sean},
title = {Removable circuits in multigraphs},
journal = {J. Combin. Theory Ser. B},
volume = {71},
number = {2},
year = {1997},
pages = {130--143},
doi = {10.1006/jctb.1997.1775},
}
@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{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},
}
@misc{aim-permutation-removable-cycle,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Removable cycles in cycle permutation graphs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/622-permutation-removable-cycle.md},
note = {Entry 622 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-00369, "Removable cycles in cycle permutation graphs", clopen.solutions.