Premium
Edge Kempe equivalence of regular graph covers
Author(s) -
Lazarovich Nir,
Levit Arie
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22500
Subject(s) - mathematics , combinatorics , edge coloring , graph , bounded function , discrete mathematics , graph coloring , enhanced data rates for gsm evolution , line graph , graph power , computer science , mathematical analysis , telecommunications
Let G be a finite d ‐regular graph with a proper edge coloring. An edge Kempe switch is a new proper edge coloring of G obtained by switching the two colors along some bichromatic cycle. We prove that any other edge coloring can be obtained by performing finitely many edge Kempe switches, provided that G is replaced with a suitable finite covering graph. The required covering degree is bounded above by a constant depending only on d .