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

For a bipartite graph $G$ with parts $X$ and $Y$, an $X$-interval coloring 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}^{\mathrm{\prime }}(G,X)$ the minimum $k$ such that $G$ has an $X$-interval coloring with $k$ colors. The author and Toft conjectured [Discrete Mathematics 339 (2016), 2628–2639] that there is a polynomial $P(x)$ such that if $G$ has maximum degree at most $\mathrm{\Delta }$, then ${\chi }_{int}^{\mathrm{\prime }}(G,X)\le P(\mathrm{\Delta })$. In this short note, we prove this conjecture; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on ${\chi }_{int}^{\mathrm{\prime }}(G,X)$ for bipartite graphs with small maximum degree.