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?

  • $\begingroup$ 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. $\endgroup$ – Dibyayan Mar 27 '14 at 16:13
  • $\begingroup$ By tight bounds by i mean if the path length is 4, then whether or not the size of the independent set is reduces. $\endgroup$ – Dibyayan Mar 27 '14 at 17:00

There are arbitrarily long sub-path whose induced subgraph contains no three independent vertices. See the graph below for length 4:

enter image description here

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.

| cite | improve this answer | |
  • $\begingroup$ Ok. If i also impose the condition that subpath of length 5 atleast one vertex which is common to all maximal cliques in that path. Then can we say something about the independence set size of the subgraph induced by this path ?? $\endgroup$ – Dibyayan Mar 29 '14 at 14:23
  • $\begingroup$ this additional condition is meaningless, because you can assume the graph has a universal vertex, which appears in every maximal clique. $\endgroup$ – Yixin Cao Mar 29 '14 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.