Recognizing vertex intersection graphs of paths on bounded degree trees

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Mazzoleni, María Pía
Formato: Articulo
Lenguaje:Inglés
Publicado: 2014
Materias:
Matemática
Intersection graphs
Recognition problems
Representations on trees
VPT graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/85561
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-85561
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
Intersection graphs
Recognition problems
Representations on trees
VPT graphs
spellingShingle Matemática
Intersection graphs
Recognition problems
Representations on trees
VPT graphs
Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
Recognizing vertex intersection graphs of paths on bounded degree trees
topic_facet Matemática
Intersection graphs
Recognition problems
Representations on trees
VPT graphs
description An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that has an (h,s,t)-representation is denoted by [h,s,t]. An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. Thus, [h,2,1] graphs are the VPT graphs that can be represented in a tree with maximum degree at most h. In this paper we characterize [h,2,1] graphs using chromatic number. We show that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete, while the problem of deciding whether the graph belongs to [h,2,1]-[h-1,2,1] is NP-hard. Both problems remain hard even when restricted to VPT∩Split. Additionally, we present a non-trivial subclass of VPT∩Split in which these problems are polynomial time solvable.
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 Recognizing vertex intersection graphs of paths on bounded degree trees
title_short Recognizing vertex intersection graphs of paths on bounded degree trees
title_full Recognizing vertex intersection graphs of paths on bounded degree trees
title_fullStr Recognizing vertex intersection graphs of paths on bounded degree trees
title_full_unstemmed Recognizing vertex intersection graphs of paths on bounded degree trees
title_sort recognizing vertex intersection graphs of paths on bounded degree trees
publishDate 2014
url http://sedici.unlp.edu.ar/handle/10915/85561
work_keys_str_mv AT alconlilianagraciela recognizingvertexintersectiongraphsofpathsonboundeddegreetrees
AT gutierrezmarisa recognizingvertexintersectiongraphsofpathsonboundeddegreetrees
AT mazzolenimariapia recognizingvertexintersectiongraphsofpathsonboundeddegreetrees
bdutipo_str Repositorios
_version_ 1764820489509797890

Ejemplares similares