# 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-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

• If $x \in V_i$ has no neighbor in $V_j$ ($i \ne j$), then $x$ cannot be in any $k$-clique. So you can remove it from the graph. Repeating this, you will end up with a trivial instance: a complete $k$-partite graph (which clearly contains a $k$-clique) or an empty graph. – Yota Otachi Sep 8 at 6:40
• @YotaOtachi Note that $i$ and $j$ are fixed. eg: Suppose only 3 classes are there $V_1,V_2$ and $V_3$. Let $x\in V_1$. Even when $x$ has no neighbor in $V_2$, it can have neighbors in $V_3$. – Cyriac Antony Sep 8 at 6:58
• Since we are looking for a clique of size $k$ in a $k$-colored graph, we need to pick one vertex from each color class $V_i$. So, each vertex picked into a $k$-clique has to have a neighbor in each color class. – Yota Otachi Sep 8 at 7:02
• @YotaOtachi Just a moment. Then, the same method should be enough to find a solution to MulticoloredClique in poly. time, right? So, something is missing for sure. – Cyriac Antony Sep 8 at 8:01
• No. You won't end up with a trivial instance in the general case. For example, consider a cycle of six vertices 1, 2, 3, 4, 5, 6 visiting them in this ordering, and partition the vertex set into {1,4}, {2,5}, {3,6}. Each vertex has a neighbor in every other color class, but this graph is clearly $K_3$ free. – Yota Otachi Sep 9 at 0:30

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.