Switching 3-edge-colorings of cubic graphs

Jan Goedgebeur; Patric R.J. Östergård

doi:10.48550/arXiv.2105.01363

Switching 3-edge-colorings of cubic graphs

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

^*Corresponding author for this work

Information Theory

Research output: Contribution to journal › Article › Scientific › peer-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 2ⁿ 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 language	English
Article number	112963
Number of pages	11
Journal	Discrete Mathematics
Volume	345
Issue number	9
DOIs	https://doi.org/10.48550/arXiv.2105.01363 https://doi.org/10.1016/j.disc.2022.112963
Publication status	Published - Sept 2022
MoE publication type	A1 Journal article-refereed

Keywords

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

Access to Document

Cite this

@article{e34af72938d74323b66ae55fb890e375,

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

keywords = "Chromatic index, Cubic graph, Edge-coloring, Edge-Kempe switching, One-factorization, Steiner triple system",

author = "Jan Goedgebeur and {\"O}sterg{\aa}rd, {Patric R.J.}",

note = "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: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = sep,

doi = "10.48550/arXiv.2105.01363",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9",

}

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

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

M1 - 112963

ER -

Switching 3-edge-colorings of cubic graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Dataset and code for Switching 3-edge-colorings of cubic graphs

Cite this

Switching 3-edge-colorings of cubic graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Datasets

Dataset and code for Switching 3-edge-colorings of cubic graphs

Cite this