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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
One-sided interval edge-colorings of bipartite graphs
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering. University of Southern Denmark, Denmark.
University of Southern Denmark, Denmark.
2016 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 339, no 11, p. 2628-2639Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2016. Vol. 339, no 11, p. 2628-2639
Keywords [en]
Interval edge-coloring; Bipartite graph; Edge coloring
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-131491DOI: 10.1016/j.disc.2016.05.003ISI: 000380593200005OAI: oai:DiVA.org:liu-131491DiVA, id: diva2:974477
Note

Funding Agencies|SVeFUM

Available from: 2016-09-26 Created: 2016-09-23 Last updated: 2017-11-21

Open Access in DiVA

fulltext(200 kB)315 downloads
File information
File name FULLTEXT01.pdfFile size 200 kBChecksum SHA-512
995ccedd1eda24310dbd7ecad25bae5f3c3f3db855a53be0893aa847a8015e90c058a3a450f6eb2818eee65401246b30cfea3363478fc00f341165e44ebbfdc1
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 316 downloads
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

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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