2
$\begingroup$

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?

$\endgroup$
2
  • $\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, 2014 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, 2014 at 17:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2014 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, 2014 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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