Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872424 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
L. Alcón, M. Gutierrez, M.P. Mazzoleni,