Armen Asratian: Some problems and results on transformations of edge colorings of graphs

Some scheduling problems can be reformulated as problems of constructing in some sense optimal proper edge colorings of a corresponding graph G. Usually such problems are very hard. Therefore it is useful to find a system of transformations which can transform any proper coloring of G to an optimal coloring of G. In this talk we discuss some results and problems on transformations of edge colorings of graphs. In particular we consider Vizing's problem, posed in 1965: Let G be a simple graph with maximum degree k which has a proper k-edge-coloring. Is it possible to obtain, from any proper t-edge-coloring of G, t > k, a proper k-edge-coloring of G using only transformations of 2-colored subgraphs such that the intermediate colorings are also proper?

We prove that it is possible if k=4. Earlier a similar result in the case k=3 was obtained by McDonald, Mohar and Scheide.  

This is joint work with Carl Johan Casselgren.