摘要：The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f â^^ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some graph. We study the Line-Graph-Edge Deletion problem, which asks whether we can delete at most k edges from the input graph G such that the resulting graph is a line graph. More precisely, we give a polynomial kernel for Line-Graph-Edge Deletion with O(kâµ) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.
关键词：Kernelization; line graphs; H-free editing; graph modification problem
