Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices 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[1]-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
The problem is polynomial-time solvable.
Observe that we have to pick exactly one vertex from each color class to form a $k$-clique.
If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{j}$ with $i \ne j$,
then no $k$-clique includes $x$. Thus, we can remove such a vertex.
Repeat this until every vertex has a neighbor in each color class (except for the class it belongs to).
If some class becomes empty, then the graph does not have a $k$-clique.
Otherwise, since the property ``every pair of color classes induces a biclique + isolated vertices''
is closed under taking induced subgraphs,
the remaining graph is a complete $k$-partite graph, which contains a $k$-clique.