Skip to main content
deleted 138 characters in body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

This would work for any perfect Cayley graph. Since we have $n$ vertices and the clique number is $\omega$, we have $n$ different $\omega$-cliques (of course several intersecting). Hence, any maximal independent set would contain at most $\lceil\frac{n}{\omega}\rceil$$\frac{n}{\omega}$ vertices in it. In fact, the vertices would be distributed equitably in $\omega$ independent sets in a $\omega$ coloring with each set having either $\lfloor\frac{n}{\omega}\rfloor$ or $\lceil\frac{n}{\omega}\rceil$ vertices. By the paper linked in the question, we have that every maximal clique intersects every maximal independent set. Therefore each disjoint maximal independent set of vertices has one vertex of each maximal clique. Thus, there are $\lfloor\frac{n}{\omega}\rfloor$$\frac{n}{\omega}$ vertex disjoint maximal cliques.

This would work for any perfect Cayley graph. Since we have $n$ vertices and the clique number is $\omega$, we have $n$ different $\omega$-cliques (of course several intersecting). Hence, any maximal independent set would contain at most $\lceil\frac{n}{\omega}\rceil$ vertices in it. In fact, the vertices would be distributed equitably in $\omega$ independent sets in a $\omega$ coloring with each set having either $\lfloor\frac{n}{\omega}\rfloor$ or $\lceil\frac{n}{\omega}\rceil$ vertices. By the paper linked in the question, we have that every maximal clique intersects every maximal independent set. Therefore each disjoint maximal independent set of vertices has one vertex of each maximal clique. Thus, there are $\lfloor\frac{n}{\omega}\rfloor$ vertex disjoint maximal cliques.

This would work for any perfect Cayley graph. Since we have $n$ vertices and the clique number is $\omega$, we have $n$ different $\omega$-cliques (of course several intersecting). Hence, any maximal independent set would contain $\frac{n}{\omega}$ vertices in it. In fact, the vertices would be distributed equitably in $\omega$ independent sets in a $\omega$ coloring. By the paper linked in the question, we have that every maximal clique intersects every maximal independent set. Therefore each disjoint maximal independent set of vertices has one vertex of each maximal clique. Thus, there are $\frac{n}{\omega}$ vertex disjoint maximal cliques.

Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

This would work for any perfect Cayley graph. Since we have $n$ vertices and the clique number is $\omega$, we have $n$ different $\omega$-cliques (of course several intersecting). Hence, any maximal independent set would contain at most $\lceil\frac{n}{\omega}\rceil$ vertices in it. In fact, the vertices would be distributed equitably in $\omega$ independent sets in a $\omega$ coloring with each set having either $\lfloor\frac{n}{\omega}\rfloor$ or $\lceil\frac{n}{\omega}\rceil$ vertices. By the paper linked in the question, we have that every maximal clique intersects every maximal independent set. Therefore each disjoint maximal independent set of vertices has one vertex of each maximal clique. Thus, there are $\lfloor\frac{n}{\omega}\rfloor$ vertex disjoint maximal cliques.