Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the degree of each vertex is at most $k$. Now consider the problem of coloring $G$'s edges with $k$ colors, such that no adjacent edges have the same color. This problem can be solved efficiently by noting that $G$ is a subgraph of a $k$-regular bipartite graph and thus one can compute a perfect matchings to color $G$.
The problem I'm trying to solve is as follows. Assume that we have colored $G_1$ and now we're given a new graph $G_2$ with the same properties and vertices of $G_1$ but with possibly different edges. We want to color $G_2$ while trying to save as many colors from $G_1$ as possible. That is, if there is an edge $e_1$ of $G_1$ that is also present in $G_2$, then we prefer to keep its color from the previous coloring of $G_1$.
Formally, suppose $c_1$ is a coloring of $G_1$ and $c_2$ is a coloring of $G_2$. Define a function $f_{c_2}$ from the edges of $G_2$ to $\{0, 1\}$ as follows: $f_{c_2}(e) = 1$ iff $e$ is present in both $G_1$ and $G_2$ and $c_1(e_1) = c_2(e_2)$. Now the problem can be stated as follows. Given $G_1$, a coloring $c_1$ of $G_1$ and given $G_2 = \langle V_2, E_2\rangle $, we're asked to compute a coloring $c_2$ of $G_2$ such that $\sum_{e \in E_2}f_{c_2}(e)$ is maximized.
My approaches:
I tried to use the Hungarian algorithm $k$ times to find $k$ perfect matchings. Lets say i want to save as many blue colored edges as possible, so i give those edges in $G_2$ a high weight, i find a perfect matching to color it with blue and then i proceed to the next color. The problem with this solution is that the order of the colors that we choose may affect the outcome.
I thought that maybe one can state the problem as an instance of LP (linear programming).
A help would be appreciated,