Paper Info
Title
Switching 3-edge-colorings of cubic graphs
Abstract
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 2(n) 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. (C) 2022 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.disc.2022.112963
DISCRETE MATHEMATICS
Keywords
DocType
Volume
Chromatic index, Cubic graph, Edge-coloring, Edge-Kempe switching, One-factorization, Steiner triple system
Journal
345
Issue
ISSN
Citations 
9
0012-365X
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Jan Goedgebeur100.34
Patric R. J. Östergård260970.61