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

Direct link
On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
University of Southern Denmark, Denmark.
2015 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 80, no 2, 83-97 p.Article in journal (Refereed) Published
Abstract [en]

A proper edge coloring of a graph with colors 1, 2, 3, ... is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is (a,b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. We prove that all (3, 6)-biregular graphs have interval colorings and that all (3, 9)-biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for (3, 5)-biregular, (4, 6)-biregular, and (4, 8)-biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings. (C) 2014 Wiley Periodicals, Inc.

Place, publisher, year, edition, pages
Wiley: 12 months , 2015. Vol. 80, no 2, 83-97 p.
Keyword [en]
biregular graph; interval edge coloring
National Category
URN: urn:nbn:se:liu:diva-121093DOI: 10.1002/jgt.21841ISI: 000359380300001OAI: diva2:852018

Funding Agencies|SVeFUM

Available from: 2015-09-07 Created: 2015-09-07 Last updated: 2015-09-09

Open Access in DiVA

fulltext(238 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 238 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

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

Direct link