Artículo
On minimal non [h,2,1] graphs
Fecha de publicación:
11/2013
Editorial:
Elsevier Science
Revista:
Electronic Notes in Discrete Mathematics
ISSN:
1571-0653
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
The class of graphs which admits a VPT representation in a host tree with maximum degree at most h is denoted by [. h, 2, 1]. The classes [. h, 2, 1] are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. In this paper we associate the minimal forbidden induced subgraphs for [. h, 2, 1] which are VPT with (color) critical graphs. We describe how to obtain minimal forbidden induced subgraphs from critical graphs, even more, we show that the family of graphs obtained using our procedure is exactly the family of minimal forbidden induced subgraphs which are VPT, split and have no dominated stable vertices. We conjecture that there are no other VPT minimal forbidden induced subgraphs. We also prove that the minimal forbidden induced subgraphs for [. h, 2, 1] that are VPT graphs belong to the class [. h+. 1, 2, 1].
Palabras clave:
FORBIDDEN SUBGRAPHS
,
INTERSECTION GRAPHS
,
REPRESENTATIONS ON TREES
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Alcón, Liliana Graciela; Gutierrez, Marisa; Mazzoleni, María Pía; On minimal non [h,2,1] graphs; Elsevier Science; Electronic Notes in Discrete Mathematics; 44; 11-2013; 115-120
Compartir
Altmétricas