# Chordal Graphs and maximum independent sets

For a chordal graph $G$ there is a clique tree such that its vertices corresponds to maximal cliques of $G$ and there is a edge between two vertices iff the intersection of the corresponding cliques are also their minimal vertex separator and for each vertex in the graph the cliques containing it, induces a subtree.

Now my questions are:-

1.Take a subpath of the tree of length 5 with the property that no vertex has degree more that 2 and intersection of all the maximal cliques is non empty. Does there exist a independent set of atleast size 3 in the subgraph induced by that vertices present in the maximal cliques taken in the path?

2.If yes, then is the bound of path length and independent set size tight?

• by "no vertex has degree more that 2" i refer to the degree in the clique tree. Take $k_{1,5}$ as the graph. Its clique tree itself can be a path and satisfies the above stated properties. Mar 27 '14 at 16:13
• By tight bounds by i mean if the path length is 4, then whether or not the size of the independent set is reduces. Mar 27 '14 at 17:00 Indeed, vertices in a sub-path induces an interval subgraph. So you can use standard interval models (the endpoints of the interval for a vertex $v$ are the indices of leftmost and rightmost bags that contain $v$) to construct the tight example easily. The graph given above have intervals: [1,1], [1,2], [1,3], [2,4], [3,4],[4,4]. Likewise, you can construct for a subpath of length n: the basic idea is that each interval either starts from 1 or ends at n.