A characterization of 2-tree probe interval graphs | Zendy

David E. Brown | Zendy; Breeann Flesch | Zendy; J. Richard Lundgren | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A characterization of 2-tree probe interval graphs

Author(s) -

David E. Brown,

Breeann Flesch,

J. Richard Lundgren

Publication year - 2014

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1754

Subject(s) - mathematics , characterization (materials science) , combinatorics , interval (graph theory) , tree (set theory) , indifference graph , interval graph , discrete mathematics , chordal graph , graph , 1 planar graph , nanotechnology , materials 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research