Change search
ReferencesLink to record
Permanent link

Direct link
On Path Factors of (3,4)-Biregular Bigraphs
Linköping University Linköping Sweden.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2008 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 24, no 5, 405-411 p.Article in journal (Refereed) Published
Abstract [en]

A (3, 4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction of such a path factor.

Place, publisher, year, edition, pages
SpringerLink , 2008. Vol. 24, no 5, 405-411 p.
Keyword [en]
Path factor, Biregular bigraph, Interval edge coloring
URN: urn:nbn:se:umu:diva-11276DOI: 10.1007/s00373-008-0803-yOAI: diva2:150947
Available from: 2008-12-05 Created: 2008-12-05 Last updated: 2011-04-28Bibliographically approved
In thesis
1. On some graph coloring problems
Open this publication in new window or tab >>On some graph coloring problems
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. 22 p.
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
National Category
Discrete Mathematics
Research subject
urn:nbn:se:umu:diva-43389 (URN)978-91-7459-198-9 (ISBN)
Public defence
2011-05-20, MIT-huset, MA121, Umeå universitet, Umeå, 13:15
Available from: 2011-04-29 Created: 2011-04-28 Last updated: 2011-05-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Graphs and Combinatorics

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: 44 hits
ReferencesLink to record
Permanent link

Direct link