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
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to