Probeinterval and probeunitintervalgraphs on superclasses of cographs

GUILLERMO ALFREDO DURÁN; LUCIANO NORBERTO GRIPPO; MARTÍN DARÍO SAFE

Bariloche

Congreso; LAGOS'11 – VI Latin-American Algorithms, Graphs and Optimization Symposium; 2011

Probe (unit) intervalgraphs form a superclass of (unit) intervalgraphs. A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) intervalgraph by adding edges with both endpoints in the set of nonprobe vertices. Probeintervalgraphs were introduced by Zhang for an application concerning with the physical mapping of DNA in the human genome project. In this work, we present characterizations by minimal forbidden induced subgraphs of probeinterval and probeunitintervalgraphs within two superclasses of cographs: P_4-tidy graphs and tree-cographs.