Probe interval and probe unit interval graphs on superclasses of cographs |
| |
| Affiliation: | 1. CONICET, Argentina;2. Depto. de Matemática, FCEN, Universidad de Buenos Aires, Argentina;3. Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Chile;4. Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina;5. Depto. de Computación, FCEN, Universidad de Buenos Aires, Argentina;1. CERDI and CRCGM, University Clermont Auvergne, Clermont-Ferrand, France;2. School of Economics & CERDI, University Clermont Auvergne, 26 Avenue Léon Blum, 63000, Clermont-Ferrand, France;3. LEO, University of Orléans, France |
| |
| Abstract: | Probe (unit) interval graphs form a superclass of (unit) interval graphs. 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) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe interval graphs 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 probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
