TY - JOUR
AU - Mkrtchyan, Vahan
PY - 2024/05/16
Y2 - 2024/11/08
TI - The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2931
UR - https://jgaa.info/index.php/jgaa/article/view/2931
SP - 129-147
AB - <pre>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. <br>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. <br>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.</pre>
ER -