On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

edge coloring problem motivated by the problem of channel assignment
in wireless networks. For an integer q >= 2 and a graph G, the goal is to
find a coloring of the edges of G with the maximum number of colors
such that every vertex of the graph sees at most q colors. This problem
is NP-hard for q = 2, and has been well-studied from the point of view of
approximation. Our main focus is the case when q = 2, which is already
theoretically intricate and practically relevant. We show fixed-parameter
tractable algorithms for both the standard and the dual parameter, and
for the latter problem, the result is based on a linear vertex kernel.

Accepted at : MFCS 2013