论文标题
识别有限树的子树的重叠图很难
Recognising the overlap graphs of subtrees of restricted trees is hard
论文作者
论文摘要
树（SOGS）中子树的重叠图概括了许多其他图形类别，具有设置表示特征。公开识别SOG的复杂性。识别许多SOG子类的复杂性是已知的。我们通过限制基础树来考虑几个SOG的子类。对于固定整数$ k \ geq 3 $，我们考虑：\ begin {my_itemize} \项目在树上有$ k $叶子的树中的子树的重叠图 \ item，树中子树的重叠图可以通过细分从给定的输入树派生，并且至少有3片叶子 \ item在树中具有最大度$ K $ \ end {my_itemize}的树中路径的重叠和交点图 我们表明，这些类的识别问题是NP库的。对于所有其他参数，我们会获得圆形图，众所周知是多项式识别的。
The overlap graphs of subtrees in a tree (SOGs) generalise many other graphs classes with set representation characterisations. The complexity of recognising SOGs in open. The complexities of recognising many subclasses of SOGs are known. We consider several subclasses of SOGs by restricting the underlying tree. For a fixed integer $k \geq 3$, we consider: \begin{my_itemize} \item The overlap graphs of subtrees in a tree where that tree has $k$ leaves \item The overlap graphs of subtrees in trees that can be derived from a given input tree by subdivision and have at least 3 leaves \item The overlap and intersection graphs of paths in a tree where that tree has maximum degree $k$ \end{my_itemize} We show that the recognition problems of these classes are NP-complete. For all other parameters we get circle graphs, well known to be polynomially recognizable.
