The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability

Abstract

A $k$-edge-coloring of a graph is an assignment of colors $\{1,...,k\}$ to edges of the graph such that adjacent edges receive different colors.
In the maximum $k$-edge-colorable subgraph problem we are given a graph and an integer $k$, the goal is to find a $k$-edge-colorable subgraph with maximum number of edges together with its $k$-edge-coloring.
In this paper, we consider the maximum 2-edge-colorable subgraph problem and present some results that deal with the fixed-parameter tractability of this problem.