2
$\begingroup$

"If S is a maximal independent set in some graph, it is a maximal clique or maximal complete subgraph in the complementary graph." from Wikipedia

Does this mean, given a graph G, if it is bipartite, then it's complement G' will have 2 maximal cliques? With, Union of vertices in these two cliques = set of all vertices in G?

example -
image

Here, Gc is bipartite, we can color it with 2 colors, and the independent groups are - {a, b, c} and {d, e}.

And so graph G (it's complement) have 2 maximal cliques {a, b, c} and {d, e}, whose union is all vertices.
So, is it true, for every graph??

$\endgroup$
2
  • $\begingroup$ An independent set in a graph is a set such that no two points in that set are connected. When you take the complement, all these points become connected to each other, that's what creates the clique. The larger the independent set, the larger the clique. I don't see what coloring has to do with this. $\endgroup$ Sep 10 '16 at 12:15
  • $\begingroup$ In a vertex coloring, the vertices of a particular color form an independent set. In the example, the nodes $a,b,c$ form an independent set in $G^c$. $\endgroup$ Sep 10 '16 at 12:24
0
$\begingroup$

Yes, if the vertex set of a graph $G$ can be partitioned into two independent sets, then the vertex set of the complete graph $G^c$ can be partitioned into two cliques (and conversely). More generally, for any subset $W \subseteq V(G)$, $W$ is an independent set of $G$ iff $W$ is a clique of $G^c$. And $W$ is a maximal independent set of $G$ iff $W$ is a maximal clique of $G^c$.

$\endgroup$
0
$\begingroup$

Suppose that $G$ is bipartite, with vertex set $V=V_0\cup V_1$, where $V_0$ and $V_1$ are the two parts. Then $V_0$ and $V_1$ are independent sets, so they will be cliques in the complement of $G$. However, they may not be maximal independent sets in $G$, so they may not be maximal cliques in the complement of $G$. Let $W_0$ be the set of vertices in $V_0$ that are adjacent to some vertex of $V_1$, and let $W_1$ be the set of vertices in $V_1$ that are adjacent to some vertex of $V_0$. Let $I=V\setminus(W_0\cup W_1)$; $I$ contains the isolated vertices of $G$. Then $W_0\cup I$ and $W_1\cup I$ are maximal independent sets in $G$ and maximal cliques in the complement of $G$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.