liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A note on transformations of edge colorings of bipartite graphs
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
2009 (English)In: JOURNAL OF COMBINATORIAL THEORY SERIES B, ISSN 0095-8956 , Vol. 99, no 5, 814-818 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
Bipartite graphs, Edge colorings, Transformations
National Category
URN: urn:nbn:se:liu:diva-19132DOI: 10.1016/j.jctb.2009.01.001OAI: diva2:223388
Available from: 2009-06-12 Created: 2009-06-12 Last updated: 2009-06-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Asratian , Amen S
By organisation
Applied MathematicsThe Institute of Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 413 hits
ReferencesLink to record
Permanent link

Direct link