Edge coloring of bipartite graphs with constraints

AbstractA classical result from graph theory states that the edges of an l-regular bipartite graph can be colored using exactly l colors so that edges that share an endpoint are assigned different colors. In this paper, we study two constrained versions of the bipartite edge coloring problem.–Some of the edges adjacent to a specific pair of opposite vertices of an l-regular bipartite graph are already colored with S colors that appear only on one edge (single colors) and D colors that appear on two edges (double colors). We show that the rest of the edges can be colored using at most max{min{l+D,3l/2},l+(S+D)/2} total colors. We also show that this bound is tight by constructing instances in which max{min{l+D,3l/2},l+(S+D)/2} colors are indeed necessary. –Some of the edges of an l-regular bipartite graph are already colored with S colors that appear only on one edge. We show that the rest of the edges can be colored using at most max{l+S/2,S} total colors. We also show that this bound is tight by constructing instances in which max{l+S/2,S} total colors are necessary