The Complexity of Consecutive $\mathrm{\Delta }$—Coloring of Bipartite Graphs: $4$ is Easy, $5$ is Hard

Abstract

For a given graph $G$ an edge-coloring of $G$ with colors $1,2,3,\dots$ 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 $\mathrm{\Delta }$ colors. We show that the above question can be answered in polynomial time for $\mathrm{\Delta }\le 4$ and becomes NP-complete if $\mathrm{\Delta }>4$.