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...
Autores principales: | , , |
---|---|
Formato: | Articulo |
Lenguaje: | Inglés |
Publicado: |
2014
|
Materias: | |
Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/85561 |
Aporte de: |
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 |