umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
Linköping University, Linköping, Sweden.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Southern Polytechnic State University, Marietta, Georgia.
University of Illinois, Urbana, Illinois.
2009 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, 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
Wiley Periodicals Inc. , 2009. Vol. 61, no 2, 88-97 p.
Keyword [en]
path factor, interval edge-coloring, biregular bipartite graph
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-25912DOI: 10.1002/jgt.20370OAI: oai:DiVA.org:umu-25912DiVA: diva2:234791
Available from: 2009-09-10 Created: 2009-09-10 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.
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Keyword
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
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
Opponent
Supervisors
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

Authority records BETA

Casselgren, Carl Johan

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of Graph Theory
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 120 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf