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

enter image description here

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?

  • $\begingroup$ In the case of this reader, I'd need a more careful formulation to understand the q. $\endgroup$ – Wlod AA Jul 11 '17 at 7:42
  • $\begingroup$ 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? $\endgroup$ – Wlod AA Jul 11 '17 at 7:47
  • 1
    $\begingroup$ Normally, these things are called "independent subsets", not colorings. $\endgroup$ – Emil Jeřábek Jul 11 '17 at 7:57
  • $\begingroup$ @WlodAA what q do you mean? $\endgroup$ – Radmir Sultamuratov Jul 11 '17 at 8:09
  • 1
    $\begingroup$ Google for "the number of independent sets in a graph". $\endgroup$ – Seva Jul 11 '17 at 8:19

Your Answer

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

Browse other questions tagged or ask your own question.