Recognising the overlap graphs of subtrees of restricted trees is hard
Main Article Content
Abstract
The overlap graphs of subtrees in a tree (SOGs) generalise many other graphs classes with set representation characterisations. The complexity of recognisingSOGs is open. The complexities of recognising many subclasses of SOGs are known. Weconsider several subclasses of SOGs by restricting the underlying tree. For afixed 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.
\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.
Article Details
How to Cite
Enright, J., & Pergel, M.
(2019).
Recognising the overlap graphs of subtrees of restricted trees is hard.
Acta Mathematica Universitatis Comenianae, 88(3), 651-658.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1198/708
Issue
Section
EUROCOMB 2019