Switching 3-edge-colorings of cubic graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 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.

Original languageEnglish
Article number112963
Number of pages11
JournalDiscrete Mathematics
Volume345
Issue number9
DOIs
Publication statusPublished - Sep 2022
MoE publication typeA1 Journal article-refereed

Keywords

  • Chromatic index
  • Cubic graph
  • Edge-coloring
  • Edge-Kempe switching
  • One-factorization
  • Steiner triple system

Fingerprint

Dive into the research topics of 'Switching 3-edge-colorings of cubic graphs'. Together they form a unique fingerprint.

Cite this