Artículo
Recognizing vertex intersection graphs of paths on bounded degree trees
Fecha de publicación:
02/2014
Editorial:
Elsevier
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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
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
Mazzoleni, María Pía; Gutierrez, Marisa; Alcón, Liliana Graciela; Recognizing vertex intersection graphs of paths on bounded degree trees; Elsevier; Discrete Applied Mathematics; 162; 2-2014; 70-77
Compartir
Altmétricas