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

Direct link
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, 2628-2639 p.Article 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, 2628-2639 p.
Keyword [en]
Interval edge-coloring; Bipartite graph; Edge coloring
National Category
Discrete Mathematics
URN: urn:nbn:se:liu:diva-131491DOI: 10.1016/j.disc.2016.05.003ISI: 000380593200005OAI: diva2:974477

Funding Agencies|SVeFUM

Available from: 2016-09-26 Created: 2016-09-23 Last updated: 2016-10-19

Open Access in DiVA

The full text will be freely available from 2018-06-06 13:17
Available from 2018-06-06 13:17

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

Direct link