Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs

An undirected 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 admit 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 under taking induced subgraphs, t...

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Mazzoleni, María Pía
Formato: Articulo
Lenguaje:Inglés
Publicado: 2015
Materias:
Matemática
Critical graphs
Forbidden subgraphs
Intersection graphs
Representations on trees
VPT graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/85830
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-85830
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Critical graphs
Forbidden subgraphs
Intersection graphs
Representations on trees
VPT graphs
spellingShingle Matemática
Critical graphs
Forbidden subgraphs
Intersection graphs
Representations on trees
VPT graphs
Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
topic_facet Matemática
Critical graphs
Forbidden subgraphs
Intersection graphs
Representations on trees
VPT graphs
description An undirected 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 admit 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 under 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) 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 VPT minimal forbidden induced subgraphs for [h,2,1]. The members of this family together with the minimal forbidden induced subgraphs for VPT (Lévêque et al., 2009; Tondato, 2009), are the minimal forbidden induced subgraphs for [h,2,1], with h ≥ 3. By taking h=3 we obtain a characterization by minimal forbidden induced subgraphs of the class V PT∩EPT=EPT∩Chordal=[3,2,2]=[3,2,1] (see Golumbic and Jamison, 1985).
format Articulo
Articulo
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 Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
title_short Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
title_full Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
title_fullStr Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
title_full_unstemmed Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
title_sort characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/85830
work_keys_str_mv AT alconlilianagraciela characterizingpathsgraphsonboundeddegreetreesbyminimalforbiddeninducedsubgraphs
AT gutierrezmarisa characterizingpathsgraphsonboundeddegreetreesbyminimalforbiddeninducedsubgraphs
AT mazzolenimariapia characterizingpathsgraphsonboundeddegreetreesbyminimalforbiddeninducedsubgraphs
bdutipo_str Repositorios
_version_ 1764820488976072706

Ejemplares similares