Edge Kempe equivalence of regular graph covers | Zendy

Lazarovich Nir | Zendy; Levit Arie | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research