One-sided interval edge-colorings of bipartite graphs

Let GG be a bipartite graph with bipartition (X,Y)(X,Y). An XX-interval coloring of GG is a proper edge-coloring of GG by integers such that the colors on the edges incident to any vertex in XX form an interval. Denote by χint′(G,X) the minimum kk such that GG has an XX-interval coloring with kk colors. In this paper we give various upper and lower bounds on χint′(G,X) in terms of the vertex degrees of GG. We also determine χint′(G,X) exactly for some classes of bipartite graphs GG. Furthermore, we present upper bounds on χint′(G,X) for classes of bipartite graphs GG with maximum degree Δ(G)Δ(G) at most 99: in particular, if Δ(G)=4Δ(G)=4, then χint′(G,X)≤6; if Δ(G)=5Δ(G)=5, then χint′(G,X)≤15; if Δ(G)=6Δ(G)=6, then χint′(G,X)≤33.