2021/06/26 by Carl Johan Casselgren, Casselgren, Carl Johan
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2106.13985
arxiv created 2021/06/26 · arxiv updated 2021/06/29
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 χ'int(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 Δ, then χ'int(G,X) ≤ P(Δ). 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 χ'int(G,X) for bipartite graphs with small maximum degree.