On Interval Colourings of Bi-Regular Bipartite Graphs

Abstract

In this paper we consider interval colourings — edge colourings of bipartite graphs in which the colours represented at each vertex form an interval of integers. These colourings, corresponding to certain types of timetables, are not always possible. In the present paper it is shown that if a bipartite graph with bipartition $(X,Y)$ has all vertices of $X$ of the same degree $d_X=2$ and all vertices of $Y$ of the same degree $d_y$, then an interval colouring can always be established.