Approximation algorithm for maximum edge coloring

We propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [Ashish Raniwala, Tzi-cker Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: INFOCOM 2005, pp. 2223–2234; Ashish Raniwala, Kartik Gopalan, Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, Mobile Comput. Commun. Rev. 8 (2) (2004) 50–65]. The problem is to color all the edges in a graph with maximum number of colors under the following q-Constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q () colors. We show that the algorithm is a 2-approximation for the case q=2 and a -approximation for the case q>2 respectively. The case q=2 is of great importance in practice. For complete graphs and trees, polynomial time accurate algorithms are found for them when q=2. The approximation algorithm gives a feasible solution to channel assignment in multi-channel wireless mesh networks.