Geodesic
The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
Vahan Mkrtchyan1
1 Gran Sasso Science Institute, School of Advanced Studies
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 129-147.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.v28i1.2931
Keywords: Edge-coloring, maximum $2$-edge-colorable subgraph, exact algorithm, fixed-parameter tractability

Vahan Mkrtchyan 1

1 Gran Sasso Science Institute, School of Advanced Studies 
@article{JGAA_2024_28_1_a5,
     author = {Vahan Mkrtchyan},
     title = {The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {129--147},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2931},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2931/}
}
TY  - JOUR
AU  - Vahan Mkrtchyan
TI  - The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 129
EP  - 147
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2931/
DO  - 10.7155/jgaa.v28i1.2931
LA  - en
ID  - JGAA_2024_28_1_a5
ER  - 
%0 Journal Article
%A Vahan Mkrtchyan
%T The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
%J Journal of Graph Algorithms and Applications
%D 2024
%P 129-147
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2931/
%R 10.7155/jgaa.v28i1.2931
%G en
%F JGAA_2024_28_1_a5
Vahan Mkrtchyan. The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 129-147. doi : 10.7155/jgaa.v28i1.2931. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2931/

Cité par Sources :