DOIAbstract
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
Add to ORKG