One-sided interval edge-colorings of bipartite graphs

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) <= 6; if Delta(G) = 5, then chi(int)' (G, X) <= 15; if Delta(G) = 6, then chi(int)' (G, X) <= 33. (C) 2016 Elsevier B.V. All rights reserved.