Edge coloring of bipartite graphs with constraints
It is a classical result from graph theory 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 diierent colors. In this paper we study two constrained versions of the bipartite edge coloring problem. { Some of the edges adjacent to a 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 in two edges (double colors). We show that the rest of the edges can be colored using at most maxfminfl+D; 3l 2 g; l+ S+D 2 g total colors. We also show that this bound is tight by constructing instances in which maxfminfl + D; 3l 2 g; l + S+D 2 g 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 maxfl + S=2; Sg total colors. We also show that this bound is tight by constructing instances in which maxfl + S=2; Sg total colors are necessary.