A Polynomial Kernel for Line Graph Deletion
Journal article, Peer reviewed
MetadataShow full item record
Original versionLeibniz International Proceedings in Informatics. 2020, 173, 1-15, 42. 10.4230/LIPIcs.ESA.2020.42
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.