umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
Linköping University, Linköping, Sweden.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Southern Polytechnic State University, Marietta, Georgia.
University of Illinois, Urbana, Illinois.
2009 (Engelska)Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 61, nr 2, s. 88-97Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Wiley Periodicals Inc. , 2009. Vol. 61, nr 2, s. 88-97
Nyckelord [en]
path factor, interval edge-coloring, biregular bipartite graph
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-25912DOI: 10.1002/jgt.20370OAI: oai:DiVA.org:umu-25912DiVA, id: diva2:234791
Tillgänglig från: 2009-09-10 Skapad: 2009-09-10 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
Ingår i avhandling
1. On some graph coloring problems
Öppna denna publikation i ny flik eller fönster >>On some graph coloring problems
2011 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Ort, förlag, år, upplaga, sidor
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. s. 22
Serie
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Nyckelord
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
urn:nbn:se:umu:diva-43389 (URN)978-91-7459-198-9 (ISBN)
Disputation
2011-05-20, MIT-huset, MA121, Umeå universitet, Umeå, 13:15
Opponent
Handledare
Tillgänglig från: 2011-04-29 Skapad: 2011-04-28 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Casselgren, Carl Johan

Sök vidare i DiVA

Av författaren/redaktören
Casselgren, Carl Johan
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Journal of Graph Theory
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 418 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf