Return to Revisions

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.