Anote on one-sided interval edge colorings of bipartite graphs
Carl Johan Casselgren · DiVA (Linkoping University) · 2022
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.