3
$\begingroup$

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?

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

0

Reset to default

Your Answer

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