The Complexity of Consecutive \(\Delta\)—Coloring of Bipartite Graphs: \(4\) is Easy, \(5\) is Hard

For a given graph \(G\) an edge-coloring of \(G\) with colors \(1,2,3,\ldots\) is said to be a \emph{consecutive coloring} if the colors of edges incident with each vertex are distinct and form an interval of integers. In the case of bipartite graphs this kind of coloring has a number of applications in scheduling theory. In this paper we investigate the question whether a bipartite graph has a consecutive coloring with \(\Delta\) colors. We show that the above question can be answered in polynomial time for \(\Delta \leq 4\) and becomes NP-complete if \(\Delta > 4\).