Switching 3-edge-colorings of cubic graphs

Jan Goedgebeur*, Patric R.J. Östergård

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

Abstrakti

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.

AlkuperäiskieliEnglanti
Artikkeli112963
Sivumäärä11
JulkaisuDiscrete Mathematics
Vuosikerta345
Numero9
DOI - pysyväislinkit
TilaJulkaistu - syysk. 2022
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki

Sukella tutkimusaiheisiin 'Switching 3-edge-colorings of cubic graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä