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

<p><img src="https://i.sstatic.net/fabQb.jpg" alt="enter image description here"></p>

<p>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.</p>

CC BY-SA 3.0
2014-03-29T14:23:38.173Z
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 ??
Dibyayan
CC BY-SA 3.0
2014-03-29T16:24:00.707Z
this additional condition is meaningless, because you can assume the graph has a universal vertex, which appears in every maximal clique.
Yixin Cao
CC BY-SA 3.0
2014-03-28T19:00:53.487Z
2014-03-28T19:13:36.347Z
2014-03-28T19:13:36.347Z
Yixin Cao
<p>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.</p>

<p>Now my questions are:- </p>

<blockquote>
  <p>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?</p>
  
  <p>2.If yes, then is the bound of path length and independent set size tight?</p>
</blockquote>

CC BY-SA 3.0
2014-03-27T16:13:34.543Z
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.
Dibyayan
CC BY-SA 3.0
2014-03-27T17:00:57.033Z
By tight bounds by i mean if the path length is 4, then whether or not the size of the independent set is reduces.
Dibyayan
<graph-theory>
Chordal Graphs and maximum independent sets
Dibyayan
# Chordal Graphs and maximum independent sets

(Asked by: username_0 on 2014-03-27)

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?

**Tags:** graph-theory

> **Comments:**
> **username_0**: 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.  
> **username_0**: By tight bounds by i mean if the path length is 4, then whether or not the size of the independent set is reduces.  

---

## 1 answers

### Answer by username_1 on 2014-03-28. Score: 2 | Accepted answer

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](https://i.sstatic.net/fabQb.jpg)

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.

> **Comments:**
> **username_0**: 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 ??  
> **username_1**: this additional condition is meaningless, because you can assume the graph has a universal vertex, which appears in every maximal clique.  

---

