A note on transformations of edge colorings of bipartite graphs

The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Δ and let t,n be integers, tnΔ. Then it is possible to obtain, from one proper edge t-coloring of G, any proper edge n-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper. In this note we show that if t>Δ then we can transform f to g using only transformations of 2-colored subgraphs. We also correct the algorithm suggested in A.S. Asratian, Short solution of Kotzig's problem for bipartite graphs, J. Combin. Theory Ser. B 74 (1998) 160–168] for transformation of f to g in the case when t=n=Δ and G is regular.