One-sided interval edge-colorings of bipartite graphs

Abstract: A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then