Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
2016 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 82, no 4, 350-373 p.Article in journal (Refereed) PublishedText
Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 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. (C) 2015 Wiley Periodicals, Inc.
Place, publisher, year, edition, pages
WILEY-BLACKWELL , 2016. Vol. 82, no 4, 350-373 p.
IdentifiersURN: urn:nbn:se:liu:diva-130653DOI: 10.1002/jgt.21906ISI: 000379956800002OAI: oai:DiVA.org:liu-130653DiVA: diva2:954247