On minimal non [h, 2, 1] graphs

A graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. 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]. In [3], it is shown that the problem of recognizing V PT graphs is polynomi...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Mazzoleni, María Pía
Formato: Objeto de conferencia Resumen
Lenguaje:Inglés
Publicado: 2013
Materias:
Ciencias Informáticas
VPT graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/94540
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-94540
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
VPT graph
spellingShingle Ciencias Informáticas
VPT graph
Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
On minimal non [h, 2, 1] graphs
topic_facet Ciencias Informáticas
VPT graph
description A graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. 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]. In [3], it is shown that the problem of recognizing V PT graphs is polynomial time solvable. In [1], it is proved that the problem of deciding whether a given VPT graph belongs to [h; 2; 1] is NP-complete even when restricted to the class V PT∏ Split without dominated stable vertices. The classes [h; 2; 1], h ≥ 2, are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. Such a family is know only for h = 2 [4] and there are some partial results for h = 3 [2]. In this paper we associate the minimal forbidden induced subgraphs for [h; 2; 1] which are VPT with (color) h-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].
format Objeto de conferencia
Resumen
author Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
author_facet Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
author_sort Alcón, Liliana Graciela
title On minimal non [h, 2, 1] graphs
title_short On minimal non [h, 2, 1] graphs
title_full On minimal non [h, 2, 1] graphs
title_fullStr On minimal non [h, 2, 1] graphs
title_full_unstemmed On minimal non [h, 2, 1] graphs
title_sort on minimal non [h, 2, 1] graphs
publishDate 2013
url http://sedici.unlp.edu.ar/handle/10915/94540
work_keys_str_mv AT alconlilianagraciela onminimalnonh21graphs
AT gutierrezmarisa onminimalnonh21graphs
AT mazzolenimariapia onminimalnonh21graphs
bdutipo_str Repositorios
_version_ 1764820491526209537

Ejemplares similares