Geodesic
Recognising the overlap graphs of subtrees of restricted trees is hard
Jessica Enright1 ; Martin Pergel2 ; Jessica Enright ; Martin Pergel
1University of Edinburgh, Easter Bush, Midlothian, UK
2Department of Software and Computer Science Education, Faculty of Mathematics and Physics Charles University, Prague, Czech Republic
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 651-658 
Jessica Enright; Martin Pergel; Jessica Enright; Martin Pergel. Recognising the overlap graphs of subtrees of restricted trees is hard. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 651-658. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a45/
@article{AMUC_2019_88_3_a45,
     author = {Jessica Enright and Martin Pergel and Jessica Enright and Martin Pergel},
     title = { Recognising the overlap graphs of subtrees of restricted trees is hard},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {651--658},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a45/}
}
TY  - JOUR
AU  - Jessica Enright
AU  - Martin Pergel
AU  - Jessica Enright
AU  - Martin Pergel
TI  - Recognising the overlap graphs of subtrees of restricted trees is hard
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 651
EP  - 658
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a45/
ID  - AMUC_2019_88_3_a45
ER  - 
%0 Journal Article
%A Jessica Enright
%A Martin Pergel
%A Jessica Enright
%A Martin Pergel
%T Recognising the overlap graphs of subtrees of restricted trees is hard
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 651-658
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a45/
%F AMUC_2019_88_3_a45

Voir la notice de l'article provenant de la source Comenius University

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.