论文标题
通过距离与低度图的最大边缘色亚图和强三元闭合参数
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
论文作者
论文摘要
给定一个无方向的图形$ g $和整数$ c $和$ k $，最大的边缘色子图问题询问我们是否可以最多删除$ g $中的最多$ k $边缘，以获取具有最多具有$ c $颜色的适当边缘着色的图形。我们表明，对于每个固定的$ c $，当通过$ g $参数为$ g $的参数为$ c-1 $的图形时，最大边缘可着色子图的最大值子图。该参数化衡量了与Viping著名定理有关的实例的距离。对于$ c \ le 4 $，我们还为多强三联闭合的相同参数化提供了线性尺寸的内核，这是社交网络分析中应用的相关边缘着色问题。我们为通过顶点删除距离到图表的最大边缘色的子图提供了进一步的结果，每个组件最多都有$ c $的顺序以及两个问题的列表色版本。
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\le 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.
