圖G的線圖是圖L（G），其頂點集是G的邊集，如果e和f在G中有一個端點，則e，f∈e（G）之間有一條邊。如果一個圖是某個圖的線圖，則稱之為線圖。本文研究了線圖的邊删除問題，即是否可以從輸入圖G中删除最多k條邊，進而得到一個線圖。更精确地說，我們給出了具有O（k5）頂點的線圖邊删除的多項式核。福蘭·科恩爾斯（FFKüners）在2013年的公開研讨會上回答了福蘭·科恩爾斯（FFKüels）在本次研讨會上提出的問題。
原文題目：A Polynomial Kernel for Line Graph Deletion
原文作者：Eduard Eiben, William Lochet
原文：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(k5) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.
原文位址：https://arxiv.org/abs/2006.15584
A Polynomial Kernel for Line Graph Deletion.pdf