Mathematicians solve 50-year-old graph theory puzzle with practical implications
Researchers have resolved a foundational problem in graph theory that has stumped mathematicians since 1965, proving how to transform complex network colorings using only simple operations. The breakthrough could improve algorithms used in network design, scheduling systems, and resource allocation across industries.
Originaltitel: Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
<p>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.</p>