Change search
ReferencesLink to record
Permanent link

Direct link
Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering. University of Southern Denmark, Denmark.
2016 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 82, no 4, 350-373 p.Article in journal (Refereed) PublishedText
Abstract [en]

Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 5 be an integer. We show that any proper t-edge coloring of G can be transformed to any proper 4-edge coloring of G using only transformations on 2-colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5-edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. (C) 2015 Wiley Periodicals, Inc.

Place, publisher, year, edition, pages
WILEY-BLACKWELL , 2016. Vol. 82, no 4, 350-373 p.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-130653DOI: 10.1002/jgt.21906ISI: 000379956800002OAI: oai:DiVA.org:liu-130653DiVA: diva2:954247
Note

Funding Agencies|SVeFUM

Available from: 2016-08-22 Created: 2016-08-19 Last updated: 2016-09-15

Open Access in DiVA

fulltext(243 kB)11 downloads
File information
File name FULLTEXT01.pdfFile size 243 kBChecksum SHA-512
4151cda6b2a0964f35edf23adc9183b2567b27ef504a9e2f7ead77be4581b792b09ff53a06e1d5997efce5957c5aa08527bb29f5207fa033ed79b64fb6d796a7
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Asratian, ArmenCasselgren, Carl Johan
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
In the same journal
Journal of Graph Theory
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 11 downloads
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: 65 hits
ReferencesLink to record
Permanent link

Direct link