Back to Search
Start Over
A CHARACTERIZATION OF 2-TREE PROBE INTERVAL GRAPHS.
- Source :
-
Discussiones Mathematicae: Graph Theory . 2014, Vol. 34 Issue 3, p509-527. 19p. 7 Black and White Photographs. - Publication Year :
- 2014
-
Abstract
- 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]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 12343099
- Volume :
- 34
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discussiones Mathematicae: Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 97078056
- Full Text :
- https://doi.org/10.7151/dmgt.1754