Some problems and results on transformations of edge colorings of graphs
Graphs, Hypergraphs, and Computing
13 February 14:00 - 15:00
Armen Asratian - Linköping University
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.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU