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

^*Tämän työn vastaava kirjoittaja

Information Theory

Tutkimustuotos: Lehtiartikkeli › Article › Scientific › vertaisarvioitu

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

Alkuperäiskieli	Englanti
Artikkeli	112963
Sivumäärä	11
Julkaisu	Discrete Mathematics
Vuosikerta	345
Numero	9
DOI - pysyväislinkit	https://doi.org/10.48550/arXiv.2105.01363 https://doi.org/10.1016/j.disc.2022.112963
Tila	Julkaistu - syysk. 2022
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Pääsy asiakirjaan

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Dataset and code for Switching 3-edge-colorings of cubic graphs
Goedgebeur, J. (Creator) & Östergård, P. (Creator), Zenodo, 2021
DOI - pysyväislinkki: 10.5281/zenodo.4707696
Tietoaineisto: Dataset

Siteeraa tätä

@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

Abstrakti

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Tietoaineistot

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

Siteeraa tätä