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

Direct link
Proper Path-Factors and Interval Edge-Coloring of (3,4)-Biregular Bigraphs
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
Umeå University.
Polytech State University, Marietta, GA.
University of Illinois.
2009 (English)In: JOURNAL OF GRAPH THEORY, ISSN 0364-9024 , Vol. 61, no 2, 88-97 p.Article in journal (Refereed) Published
Abstract [en]

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph.

Place, publisher, year, edition, pages
2009. Vol. 61, no 2, 88-97 p.
Keyword [en]
path factor, interval edge-coloring, biregular bipartite graph
National Category
URN: urn:nbn:se:liu:diva-18555DOI: 10.1002/jgt.20370OAI: diva2:220587
Available from: 2009-06-01 Created: 2009-06-01 Last updated: 2009-06-01

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Asratian, Armen
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: 384 hits
ReferencesLink to record
Permanent link

Direct link