I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent sets $V_1,V_2,\dots,V_k$).
MulitColoredClique with Simple Modules
Instance: A graph $G$, an integer $k$, and a $k$-coloring $V_1,V_2,\dots,V_k$ of $G$ such that
$\quad\qquad\;\ $for every pair of colors $i$ and $j$, $V_i\cup V_j$ induces the disjoint union of
$\quad\qquad\;\ $ a complete bipartite graph with an independent set.
(in other words, if $x\in V_i$ has a neighbor in $V_j$, and $y\in V_j$ has a neighbor in $V_i$, then $x$ and $y$ are neighbors).
Question: Is there a clique of size $k$ in $G\,?$
Is this problem NP-hard? (or even W-hard?)
I have a feeling that it is indeed NP-hard, but I am unable to prove it.
Or, is this problem in P?
If it is in P, an interesting combinatorial problem will also be in P.
Is this or any related problem (other than MultiColoredClique) studied in the literature?
PS: Sorry, I asked the wrong question. Somehow, I assumed that bipartite complement of biclique+isolated vertices was again biclique+isolated vertices. What I wanted to ask is here: Complement of Multi-colored Clique with an extra condition