Anote 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) (G, X) the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial P(Delta) such that if G has maximum degree at most A, then chi'(int)(G, X) <= P(A). In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on chi'(int)(G, X) for bipartite graphs with small maximum degree. (C) 2021 The Author(s). Published by Elsevier B.V.

Automated summary

This note affirms the existence of a cubic polynomial for X-interval coloring and deduces improved upper bounds for bipartite graphs with small maximum degree. The authors provide a positive answer to the question posed by Casselgren and Toft (2016), demonstrating that the X-interval coloring can be achieved with a polynomial of degree three.