liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
One-sided interval edge-colorings of bipartite graphs
Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten. University of Southern Denmark, Denmark.
University of Southern Denmark, Denmark.
2016 (Engelska)Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 339, nr 11, s. 2628-2639Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Let G be a bipartite graph with bipartition (X, Y). An X-interval coloring of G is a proper edge-coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int)(G, X) the minimum k such that G has an X-interval coloring with k colors. In this paper we give various upper and lower bounds on chi(int)(G, X) in terms of the vertex degrees of G. We also determine chi(int) (G, X) exactly for some classes of bipartite graphs G. Furthermore, we present upper bounds on chi(int) (G, X) for classes of bipartite graphs G with maximum degree Delta(G) at most 9: in particular, if Delta(G) = 4, then chi(int) (G, X) amp;lt;= 6; if Delta(G) = 5, then chi(int) (G, X) amp;lt;= 15; if Delta(G) = 6, then chi(int) (G, X) amp;lt;= 33. (C) 2016 Elsevier B.V. All rights reserved.

Ort, förlag, år, upplaga, sidor
ELSEVIER SCIENCE BV , 2016. Vol. 339, nr 11, s. 2628-2639
Nyckelord [en]
Interval edge-coloring; Bipartite graph; Edge coloring
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-131491DOI: 10.1016/j.disc.2016.05.003ISI: 000380593200005OAI: oai:DiVA.org:liu-131491DiVA, id: diva2:974477
Anmärkning

Funding Agencies|SVeFUM

Tillgänglig från: 2016-09-26 Skapad: 2016-09-23 Senast uppdaterad: 2017-11-21

Open Access i DiVA

fulltext(200 kB)371 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 200 kBChecksumma SHA-512
995ccedd1eda24310dbd7ecad25bae5f3c3f3db855a53be0893aa847a8015e90c058a3a450f6eb2818eee65401246b30cfea3363478fc00f341165e44ebbfdc1
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Casselgren, Carl Johan
Av organisationen
Matematik och tillämpad matematikTekniska fakulteten
I samma tidskrift
Discrete Mathematics
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 372 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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