Recognizing [h,2,1] graphs

Details Recognizing [h,2,1] graphs Recognizing [h,2,1] graphs

2011-12-14

arxiv.org/abs/1112.3254v1

Mathematics

Combinatorics

Scientific paper

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 mots 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 have an (h,s,t)-representation is denoted [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. 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 $Split \cap VPT$. Additionally, we present a non-trivial subclass of $Split \cap VPT$ in which these problems are polynomial time solvable.

Affiliated with

Also associated with

No associations

Rating

Recognizing [h,2,1] graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Recognizing [h,2,1] graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recognizing [h,2,1] graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-227751