A characterization of 2-tree probe interval graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 509-527
Voir la notice de l'article provenant de la source Library of Science
A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231]
Keywords:
interval graph, probe interval graph, 2-tree
@article{DMGT_2014_34_3_a3,
author = {Brown, David E. and Flesch, Breeann M. and Lundgren, J. Richard},
title = {A characterization of 2-tree probe interval graphs},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {509--527},
publisher = {mathdoc},
volume = {34},
number = {3},
year = {2014},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a3/}
}
TY - JOUR AU - Brown, David E. AU - Flesch, Breeann M. AU - Lundgren, J. Richard TI - A characterization of 2-tree probe interval graphs JO - Discussiones Mathematicae. Graph Theory PY - 2014 SP - 509 EP - 527 VL - 34 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a3/ LA - en ID - DMGT_2014_34_3_a3 ER -
%0 Journal Article %A Brown, David E. %A Flesch, Breeann M. %A Lundgren, J. Richard %T A characterization of 2-tree probe interval graphs %J Discussiones Mathematicae. Graph Theory %D 2014 %P 509-527 %V 34 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a3/ %G en %F DMGT_2014_34_3_a3
Brown, David E.; Flesch, Breeann M.; Lundgren, J. Richard. A characterization of 2-tree probe interval graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 509-527. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a3/