Premium
Solution of Vizing's Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
Author(s) -
Asratian Armen S.,
Casselgren* Carl Johan
Publication year - 2016
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.21906
Subject(s) - mathematics , combinatorics , degree (music) , edge coloring , graph , discrete mathematics , brooks' theorem , class (philosophy) , 1 planar graph , graph power , line graph , computer science , physics , artificial intelligence , acoustics
Let G be a Class 1 graph with maximum degree 4 and let t ≥ 5 be an integer. We show that any proper t ‐edge coloring of G can be transformed to any proper 4‐edge coloring of G using only transformations on 2‐colored subgraphs (so‐called interchanges). This settles the smallest previously unsolved case of a well‐known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5‐edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7‐edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent.