An FPT Algorithm for Maximum Edge Coloring

Each node in a wireless network has two interface cards, and the goal is to use as many frequency channels as possible. In graph terms, color the edges with as many colors as you can so that no vertex sees more than two. This Maximum Edge 2-Coloring problem is NP-hard and APX-hard, and earlier work has looked at approximation. I take the parameterized view: an FPT algorithm for the number of colors k, which branches on colors around a vertex cover and finishes with a matching computation, and a linear vertex kernel for the dual question of using at least n − k colors. I also discuss open problems.