Probe interval and probe unit interval graphs on superclasses of cographs

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 (un...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Durán, Guillermo A., Grippo, Luciano Norberto, Safe, Martín Darío
Publicado:	2011
Materias:	Forbidden induced subgraphs P4-tidy graphs Probe interval graphs Probe unit interval graphs Tree-cographs
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p339_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p339_Duran
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v37_nC_p339_Duran
record_format	dspace
spelling	paper:paper_15710653_v37_nC_p339_Duran2025-07-30T19:00:06Z Probe interval and probe unit interval graphs on superclasses of cographs Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Forbidden induced subgraphs P4-tidy graphs Probe interval graphs Probe unit interval graphs Tree-cographs 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. © 2011 Elsevier B.V. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p339_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p339_Duran
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Forbidden induced subgraphs P4-tidy graphs Probe interval graphs Probe unit interval graphs Tree-cographs
spellingShingle	Forbidden induced subgraphs P4-tidy graphs Probe interval graphs Probe unit interval graphs Tree-cographs Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío Probe interval and probe unit interval graphs on superclasses of cographs
topic_facet	Forbidden induced subgraphs P4-tidy graphs Probe interval graphs Probe unit interval graphs Tree-cographs
description	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. © 2011 Elsevier B.V.
author	Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_facet	Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_sort	Durán, Guillermo A.
title	Probe interval and probe unit interval graphs on superclasses of cographs
title_short	Probe interval and probe unit interval graphs on superclasses of cographs
title_full	Probe interval and probe unit interval graphs on superclasses of cographs
title_fullStr	Probe interval and probe unit interval graphs on superclasses of cographs
title_full_unstemmed	Probe interval and probe unit interval graphs on superclasses of cographs
title_sort	probe interval and probe unit interval graphs on superclasses of cographs
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p339_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p339_Duran
work_keys_str_mv	AT duranguillermoa probeintervalandprobeunitintervalgraphsonsuperclassesofcographs AT grippolucianonorberto probeintervalandprobeunitintervalgraphsonsuperclassesofcographs AT safemartindario probeintervalandprobeunitintervalgraphsonsuperclassesofcographs
_version_	1840323172699734016

Probe interval and probe unit interval graphs on superclasses of cographs

Ejemplares similares