On interval edge-colorings of bipartite graphs

An edge-coloring of a graph G with colors 1,..., t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of interval colorable graphs is denoted by R. Recently, Toft has conjectured that all bipartite graphs with maximum degree at most 4 are interval colorable. In this paper we prove that: 1) if G is a bipartite graph with Δ(G) ≤ 4, then G□K₂ N R; 2) if G is a bipartite graph with Δ (G) = 5 and without a vertex of degree 3, then G□K₂ N R; 3) if G is a bipartite graph with Δ(G) = 6 and it has a 2-factor, then G□K₂ N N. In 1999, Giaro using computer-aided methods showed that all bipartite graphs on at most 14 vertices are interval colorable. On the other hand, the smallest known examples of interval non-colorable bipartite graphs have 19 vertices. In this paper we also observe that several classes of bipartite graphs of small order have an interval coloring. In particular, we show that all bipartite graphs on 15 vertices are interval colorable.