A note on one-sided interval edge colorings of bipartite graphs (Q2666587)

For a proper edge coloring \(\varphi\) of a graph \(G\) and \(v \in V(G)\) the palette of \(v\), \(\varphi(v)\), is the set of colors appearing on edges incident to \(v\). An interval coloring of a graph \(G\) is a proper edge coloring by integers such that the palette of \(v\) is an interval of integers for any \(v \in V(G)\). For a bipartite graph \(G=(X,Y; E)\) with parts \(X\) and \(Y\) and edge set \(E=E(G)\), an \(X\)-interval coloring of \(G\) is a proper edge coloring such that the palette of \(v\) is an interval of integers for any \(v \in X\). The smallest integer \(t\) for which there is an \(X\)-interval \(t\)-coloring of \(G\) is denoted by \(\chi_{\textrm{int}}^\prime(G,X)\). The invariant is motivated by the problem of finding a timetable where lectures of either teachers or classes are scheduled at consecutive times. The author proves that there exists a cubic polynomial \(P(\Delta)\) such that for every bipartite graph \(G=(X,Y;E)\) with maximum degree \(\Delta\), \(\chi_{\textrm{int}}^\prime(G,X) \leq P(\Delta)\). This bound is then improved for particular families of bipartite graphs. It is proved that \(\chi_{\textrm{int}}^\prime(G,X) \leq 17\) in any bipartite graph \(G=(X,Y;E)\) with \(\Delta(G)=6\).