Improved Approximation Algorithms for
Weighted Edge Coloring of Graphs

Let the current open bin be $b_{1}$ which already has $c$ weight in it and at this instant a new item $i$ of weight $w_{i}$ arrives. If a new bin is required for accommodating item $i$, then we must have $c+w_{i}>1$, else a new bin won’t be required. Let the new bin be $b_{2}$. We then close the current bin $b_{1}$ and we fit the item $i$ in $b_{2}$. The final weight in $b_{2}$ will be $\geq w_{i}$. So, the sum of weights in $b_{1}$ and $b_{2}$ is atleast $c+w_{i}>1$. In the same way, in general the sum of final weights of any 2 consecutive bins is greater than 1. Now assume on contradiction, that at some instant, there is a requirement for opening the $2m^{th}$ bin, then the total weight of all the items which have already arrived will be greater than $m$, which is a contradiction.

Assign $t$ open bins at the start, named $c_{1},c_{2},...,c_{t}$, where bin $c_{i}$ would accommodate items of type $i$. On the arrival of an item of type $i$, if the current bin $c_{i}$ is unable to fit the item, then close the bin $c_{i}$, and replace it with another new bin, which will now be named $c_{i}$. Place the item in this new bin of type $i$. Carry on this procedure for all items.
At last there will be $t$ open bins, and the number of closed bins will be $<2m$. Otherwise, if number of closed bins is $\geq 2m$, then it would be a contradiction to the $2m-1$ bound guaranteed by Lemma 2.1. This is because here we are essentially following the same rules as standard NEXT-FIT, the only difference is upon arrival of an item of type $i$, we are checking the bin $c_{i}$ instead of a common open bin for all items in standard NEXT-FIT. Using the standard NEXT-FIT, first produce the items of type 1, then type 2 and so on till type $t$. So, if $\geq 2m$ closed bins are required, then in this case also $\geq 2m$ will be required contradicting Lemma 2.1. Thus, overall we need at most $2m-1+t$ different bins for all items under this scenario. In other words, at most $2m-1$ closed bins as we have exactly $t$ open bins.

The number of open bins is clearly at most $t$ because $w$ has at most $t$ neighbours. So, specifically, we need to show that number of closed bins used by $w$ is at most $2m-1$. Actually, this follows directly from Lemma 3.1. We can relate the $t$ types in Lemma 3.1 with $t$ neighbours here, and the items with the edges.

We will prove it by contradiction. Let at an instant, edge $e$ incident to $w$ arrive which causes it’s $2m^{th}$ bin to close in order to fit edge $e$. The claim is that such an instant can $never$ occur. Let suppose such an incident indeed occur. Now, take all the items which were previously packed in the $2m$ closed bins and the item $e$. Then, imagine producing all these items (i.e. edges) in the same order as they arrive in the original graph scenario, and try to pack these items using NEXT-FIT along with the condition that there are $t$ types (corresponding to $t$ neighbour vertices) and items of 2 different types cannot be placed together. We would then have to close the $2m^{th}$ when the item $e$ arrives leading to $2m$ closed bins, which is a contradiction to Lemma 3.1.

When using NEXT-FIT, let at an instant, edge $e=(u,v)$ arrive, and let $g_{1}$ = number of closed bins used by $u$ and $g_{2}$ = number of closed bins used by $v$ and let bin $c$ be the current open bin between $u$ and $v$, all just before arrival of edge $e$.

If edge $e$ is able to fit in bin $c$, then fit edge $e$ in bin $c$ and continue. Else, close bin $c$. Replace it with a new bin and fit edge $e$ in the new bin.

Now, we need to prove that if we have a palette of $4m+2t$ colors, then the new bin can be found from this palette without any violations. In other words, $4m+2t$ colors are sufficient. From Lemma 3.4, we have $g_{1}$ $<$ $2m$ and $g_{2}$ $<$ $2m$. Vertex $u$ has at most $t$ open bins and vertex $v$ has at most $t$ open bins just before arrival of $e$. So, just before arrival of $e$, the sum of closed and open bins for both vertices $u$ and $v$ is $g_{1}+g_{2}+2t$ $\leq$ $2m-1+2m-1+2t=4m-2+2t$ (It is indeed $4m-2+2t-1$ because of the common open bin between $u$ and $v$). So, given our pool of $4m+2t$ colors, we will always be able to find a new color without any violations to either vertices. Also, $u$ and $v$ are the only vertices where a violation can occur at this step and thus we care about only these.

If a new bin is selected, then $g_{1}$ and $g_{2}$ both increments by $1$ but the number of open bins for both remains at most $t$. Though $g_{1}$ and $g_{2}$ increase by $1$, it is guaranteed that they never reach $2m$. Because it would be a violation to Lemma 3.4 as then $g_{1}=2m$ $>$ $2m-1$, contradicting Lemma 3.4.

In other words, the above arguments imply that if a specific vertex has $2m-1$ closed bins, then none of it’s $t$ open bins will be forced to close. Because a bin is closed only when another new bin in opened and thus leading to a contradiction of Lemma 3.4.

Finally, we can say that $4m+2t$ colors are enough (indeed $4m-1+2t$ colors are enough). The bound $1.693\cdot 2m-1+24t$ directly follows for $HARMONIC_{M}$ (with $M=12$) with the exact same arguments as above, just replace $t$ with $12t$ and $2m$ with $1.693m$. Also as described in Algorithm 2, take into account the type of edge arriving. An edge $e=(u,v)$ of type $i$ must be fit into the open bin of type $i$ between $u$ and $v$.

We have a palette $P$ of $m+1$ colors numbered from 1 to $m+1$. Consider a simpler example where we are given an undirected simple graph $T$ with no cycles that is $T$ is a undirected simple tree. Let vertex $r$ be the root vertex (if not given, choose any vertex as $r$). We will traverse $T$ in a BFS manner starting from the root node $r$. Whenever visiting a node $u$, we will color the edges incident to it.

Consider any step of this traversal where we visit node $u$. Let the $k$ child nodes of $u$ be $v_{1},v_{2},\dots,v_{k}$ and let $w$ be the parent node of $u$ (if $u\neq r$). As we are traversing in a BFS manner, the edge $(w,u)$ must have been already colored and none of the edges $(u,v_{1}),(u,v_{2}),\dots,(u,v_{k})$ are colored (which we have to color in this step). So, with respect to $u$, its only one of the incident edges have been colored. So, by the definition of $m$, all the remaining edges incident to $u$ can be colored taking at most $m$ colors in total from palette $P$. This will not create any violations in any of the child nodes, as only one of the edges of each child node is colored in this step. Carry on this procedure for each node visited and eventually we have colored all the edges of the tree. Thus, we can properly color a undirected simple tree in $m$ colors.

Now if we also have edge disjoint cycles, then this case is very similar to the above. The only difference is that when visiting a node $u$, it might happen that two of its edges have already been assigned different colors. But it might happen that the optimal packing of edges incident to $u$ in $m$ unit-sized bins assign same colors to these two already colored edges or vice-versa. It might also happen that when we color the edges between the current vertex and any of its child node, a clash might occur at the child node. This is because now 2 edges of a child node may be colored before visiting that child node which may create a violation. Thus we place an extra color in palette $P$ to overcome this violation. Thus, $m+1$ colors are sufficient in this case.

This result can be further generalised. If we are given an undirected simple graph $G$. Let $y$ be the maximum number of cycles an edge is a part of taken over all the edges. Then while traversing the graph in a BFS manner, it may happen that $y+1$ edges have already been colored. So, in the worst case scenario, we would require $m+y$ colors for properly coloring all the edges in this case.

Let $r$ be the root vertex (assign any of the vertex as root vertex randomly if $r$ not specified). Below we present the algorithms achieving the above upper bounds along with their analysis. The algorithm starts from the root vertex and visits all the nodes in a BFS manner. When visiting a node, it colors the edges incident to it.

First let us consider when we use NEXT-FIT. Let there be a palette $P$ having $2m$ colors numbered from 1 to $2m$. Whenever a new color is required from $P$, we chose the least numbered color which does not create any violations. We claim that the size of $P$ is sufficient to properly color all the edges. When visiting a node $u$. Let the $k$ child nodes of $u$ be $v_{1},v_{2},\dots,v_{k}$ and let vertex $w$ be the parent node of $u$ if $u$ is not the root vertex. As we are traversing in a BFS manner, none of the edges between $u$ and its child node $v_{i}$ will be colored (they have to be colored in this step) whereas the edges between $u$ and parent node $w$ must have already been colored when $w$ was visited.

We will color the edges between $u$ and its child nodes in a specific order in which we consider one child node at a time and color the edges between them. First color the edges between $u$ and $v_{1}$ in a NEXT-FIT manner. This means that at any moment there is an active/open color between $u$ and $v_{1}$ and present the edges between them in an online fashion (though we have all the edges beforehand) and color them using NEXT-FIT. As the edges between $u$ and $w$ have already been colored, let the colors used for them be numbered from $c_{1}$ to $c_{2}$. Note that it would a continuous range of colors due to the way we are coloring the edges each child node at a time, and the way of choosing the new color when required from palette $P$. Keep $c_{2}$ as the initial open color between $u$ and $v_{1}$ and carry on the procedure as explained above. When all the edges between $u$ and $v_{1}$ have been colored, let the colors used for this be numbered from $c_{2}$ to $c_{3}$. Now move on to the next child node $v_{2}$ with $c_{3}$ as the initial open color between them. Carry on the this procedure for all the child nodes of $u$.

We claim that if the above algorithm is followed, then the number of colors used by $u$ will be atmost $2m$ which are taken from palette $P$ without creating any violations. This can be seen with the help of Lemma 2.1. Lemma 2.1 claims that when items are presented in an online manner and we pack them using NEXT-FIT, then atmost $2m-1$ bins are required. It is an easy observation that we are doing the same thing here when visiting vertex $u$. The items are the edges and the bins are the colors. As $w$ is the parent node of $u$, $w$ must have been visited earlier than $u$. At that step when considering the edges between $w$ and $u$, following the above algorithm, these edges are presented in an online manner and colored using NEXT-FIT. So, when we visit $u$ in the current step, some of its edges have already been colored using NEXT-FIT, and now we color the remaining incident edges again using NEXT-FIT. Thus, the overall effect with respect to $u$ is that all its incident edges are colored in a NEXT-FIT manner thus taking atmost $2m-1+1$ colors. The $+1$ term is there because the first color ($c_{1}$ in the above example) might not be fully utilized with respect to $u$. This holds true for any node $u$ visited during BFS traversal. And thus by induction, all the edges of $G$ can be colored properly using only the colors from palette $P$.

Finally for the case when we use $HARMONIC_{M}$ (with $M=12$), the algorithm and analysis is very similar to the above. The only differences are that now we follow $HARMONIC_{M}$ packing, by taking into consideration the $M$ types of items/edges. So, at any moment there would be $M=12$ open bins instead of just 1, each corresponding to a unique type. From Lemma 2.3, the upper bound guarantee is $1.693m$. So, the palette size of $1.693m+12$ will be sufficient for properly coloring all the edges without any violations. Below we present both the algorithms in a concise form.