A note on transformations of edge colorings of bipartite graphs
2009 (English)In: JOURNAL OF COMBINATORIAL THEORY SERIES B, ISSN 0095-8956 , Vol. 99, no 5, 814-818 p.Article in journal (Refereed) Published
The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Delta and let t, n be integers, t andgt;= n andgt;= Delta. 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 andgt; Delta 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 Kotzigs problem for bipartite graphs, J. Combin. Theory Set. B 74 (1998) 160-168] for transformation of f to g in the case when t = n = Delta and G is regular.
Place, publisher, year, edition, pages
2009. Vol. 99, no 5, 814-818 p.
Bipartite graphs, Edge colorings, Transformations
IdentifiersURN: urn:nbn:se:liu:diva-19132DOI: 10.1016/j.jctb.2009.01.001OAI: oai:DiVA.org:liu-19132DiVA: diva2:223388