# A Characterization of 2-Tree Probe Interval Graphs

David E. Brown; Breeann M. Flesch; J. Richard

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 3, page 509-527
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDavid E. Brown, Breeann M. Flesch, and J. Richard. "A Characterization of 2-Tree Probe Interval Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 509-527. <http://eudml.org/doc/268020>.

@article{DavidE2014,

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]},

author = {David E. Brown, Breeann M. Flesch, J. Richard},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {interval graph; probe interval graph; 2-tree},

language = {eng},

number = {3},

pages = {509-527},

title = {A Characterization of 2-Tree Probe Interval Graphs},

url = {http://eudml.org/doc/268020},

volume = {34},

year = {2014},

}

TY - JOUR

AU - David E. Brown

AU - Breeann M. Flesch

AU - J. Richard

TI - A Characterization of 2-Tree Probe Interval Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 509

EP - 527

AB - 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]

LA - eng

KW - interval graph; probe interval graph; 2-tree

UR - http://eudml.org/doc/268020

ER -

## References

top- [1] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory 9 (1970) 129-135. doi:10.1016/S0021-9800(70)80019-9[Crossref] Zbl0202.55702
- [2] L.W. Beineke and R.E. Pippert, Properties and characterizations of k-trees, Math- ematika 18 (1971) 141-151. doi:10.1112/S0025579300008500[Crossref] Zbl0221.05057
- [3] D.E. Brown, Variations on Interval Graphs, PhD Thesis, (Univ. of Colorado, Den- ver, USA, 2004).
- [4] D.E. Brown, A.H. Busch and G. Isaak, Linear time recognition algorithms and struc- ture theorems for bipartite tolerance graphs and bipartite probe interval graphs, Dis- crete Math. Theor. Comput. Sci. 12(5) (2010) 63-82. Zbl1280.68142
- [5] D.E. Brown, S.C. Flink and J.R. Lundgren, Interval k-graphs, in: Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002) 156 (2002) 5-16. Zbl1022.05073
- [6] D.E. Brown and L.J. Langley, Forbidden subgraph characterizations of bipartite unit probe interval graphs, Australas. J. Combin. 52 (2012) 19-31. Zbl1251.05133
- [7] D.E. Brown and J.R. Lundgren, Bipartite probe interval graphs, circular arc graphs, and interval point bigraphs, Australas. J. Combin. 35 (2006) 221-236. Zbl1095.05030
- [8] D.E. Brown, J.R. Lundgren and L. Sheng, A characterization of cycle-free unit probe interval graphs, Discrete Appl. Math. 157 (2009) 762-767. doi:10.1016/j.dam.2008.07.004[WoS][Crossref] Zbl1172.05345
- [9] P.C. Fishburn, Interval Orders and Interval Graphs (Wiley & Sons, 1985).
- [10] B. Flesch and J.R. Lundgren, A characterization of k-trees that are interval p-graphs, Australas. J. Combin. 49 (2011) 227-237. Zbl1228.05219
- [11] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835-855. doi:10.2140/pjm.1965.15.835[Crossref] Zbl0132.21001
- [12] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
- [13] M.C. Golumbic and M. Lipshteyn, On the hierarchy of interval, probe and tolerance graphs, in: Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001) 153 (2001) 97-106. Zbl0995.05104
- [14] M.C. Golumbic and A.N. Trenk, Tolerance Graphs, Cambridge Studies in Advanced Mathematics, Vol. 18 (Cambridge University Press, Cambridge, 2004). Zbl1091.05001
- [15] C.G. Lekkerkerker and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962/1963) 45-64. Zbl0105.17501
- [16] R. McConnell and Y. Nussbaum, Linear-time recognition of probe interval graphs, in: Proceedings of the 17th Annual European Symposium, Algorithms-ESA 2009, Lecture Notes in Comput. Sci. 5757 (2009) 349-360. doi:10.1007/978-3-642-04128-0 32[Crossref] Zbl1256.05236
- [17] F.R. McMorris, C. Wang and P. Zhang, On probe interval graphs, Discrete Appl. Math. 88 (1998) 315-324. doi:10.1016/S0166-218X(98)00077-8[Crossref] Zbl0918.05087
- [18] A. Proskurowski, Separating subgraphs in k-trees: cables and caterpillars, Discrete Math. 49 (1984) 275-285. doi:10.1016/0012-365X(84)90164-X[Crossref]
- [19] N. Pržulj and D.G. Corneil, 2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150 (2005) 216-231. doi:10.1016/j.dam.2004.06.015[Crossref]
- [20] F.S. Roberts, Discrete Mathematical Models (Prentice-Hall, Upper Saddle River, NJ, 1976).
- [21] L. Sheng, Cycle free probe interval graphs, in: Proceedings of the Thirtieth South- eastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999) 140 (1999) 33-42. Zbl0960.05085
- [22] P. Zhang, Methods of mapping DNA fragments, United States Patent, 1997 http://www.cc.columbia.edu/cu/cie/techlists/patents/5667970.htm
- [23] P. Zhang, E.A. Schon, E. Cayanis, J.Weiss, S. Kistler and P.E. Bourne, An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA, Comput. Appl. Biosci. 10(3) (1994) 309-317.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.