Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
share
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 proper edge coloring with at most c colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed c, a linear-size problem kernel when parameterized by the edge deletion distance of G to a graph with maximum degree c-1. This parameterization measures the distance to instances that, due to Vizing's famous theorem, are trivial yes-instances. For c< 4, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most c and for the list-colored versions of both problems.
READ FULL TEXT