# What is the number of independent sets in graph of this type?

Suppose we have a graph $G(V,E)$

What is the number of independent sets in graph of this type?

I have an idea to use reccurence $$|G|=|G\backslash \{v\}|+|G\backslash n(v)|$$ where $|G|$ is the number all possible independent sets of graph G, $v$ is an arbitrary vertex, and $n(v)$ is a set of all vertex's adjacent with $v$ and $v$ itself.

But may be there some better ideas or results?

• In the case of this reader, I'd need a more careful formulation to understand the q. – Wlod AA Jul 11 '17 at 7:42
• Consider (linear) graph: # --- # --- # --- #, and let A B C D be different colors. Is A --- B --- C --- D a tolerant coloring? Is A --- A --- A --- A tolerant? – Wlod AA Jul 11 '17 at 7:47
• Normally, these things are called "independent subsets", not colorings. – Emil Jeřábek Jul 11 '17 at 7:57
• @WlodAA what q do you mean? – Radmir Sultamuratov Jul 11 '17 at 8:09
• Google for "the number of independent sets in a graph". – Seva Jul 11 '17 at 8:19