TY - JOUR
T1 - Switching 3-edge-colorings of cubic graphs
AU - Goedgebeur, Jan
AU - Östergård, Patric R.J.
N1 - Funding Information:
We would like to thank Gunnar Brinkmann for useful suggestions. The observation at the end of Section 2 dates back to discussions with Petteri Kaski after the publication of [26] . Several of the computations for this work were carried out using the supercomputer infrastructure provided by the VSC (Flemish Supercomputer Center), funded by the Research Foundation Flanders (FWO) and the Flemish Government. The research of Jan Goedgebeur was supported by Internal Funds of KU Leuven .
Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022/9
Y1 - 2022/9
N2 - The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switching, which can be used to transform edge-colorings, is here considered for 3-edge-colorings of cubic graphs. Computational results for edge-Kempe switching of cubic graphs up to order 30 and bipartite cubic graphs up to order 36 are tabulated. Families of cubic graphs of orders 4n+2 and 4n+4 with 2n edge-Kempe equivalence classes are presented; it is conjectured that there are no cubic graphs with more edge-Kempe equivalence classes. New families of nonplanar bipartite cubic graphs with exactly one edge-Kempe equivalence class are also obtained. Edge-Kempe switching is further connected to cycle switching of Steiner triple systems, for which an improvement of the established classification algorithm is presented.
AB - The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switching, which can be used to transform edge-colorings, is here considered for 3-edge-colorings of cubic graphs. Computational results for edge-Kempe switching of cubic graphs up to order 30 and bipartite cubic graphs up to order 36 are tabulated. Families of cubic graphs of orders 4n+2 and 4n+4 with 2n edge-Kempe equivalence classes are presented; it is conjectured that there are no cubic graphs with more edge-Kempe equivalence classes. New families of nonplanar bipartite cubic graphs with exactly one edge-Kempe equivalence class are also obtained. Edge-Kempe switching is further connected to cycle switching of Steiner triple systems, for which an improvement of the established classification algorithm is presented.
KW - Chromatic index
KW - Cubic graph
KW - Edge-coloring
KW - Edge-Kempe switching
KW - One-factorization
KW - Steiner triple system
UR - http://www.scopus.com/inward/record.url?scp=85129518685&partnerID=8YFLogxK
U2 - 10.48550/arXiv.2105.01363
DO - 10.48550/arXiv.2105.01363
M3 - Article
AN - SCOPUS:85129518685
VL - 345
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 9
M1 - 112963
ER -