Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs

Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz

Given an undirected graph $G$ and integers $c$ and $k$, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most $k$ edges in $G$ to obtain a graph that has a…