A graph is $(p,q)$-colorable if its vertices can be partitionedinto $p$ cliques and $q$ independent sets.For $(2,0)$-colorable graphs clique is polynomial.I am interested how easier (if any) is clique in $(3,0)$-colorable,when the partitions are given.Given graph $G$ and 3 partitions of its vertices $A,B,C : A \cup B \cup C=V(G)$ suchthat $A,B,C$ induce cliques in G.Q1 Is clique faster in this case?Q2 If it is faster what is the complexity?Q3 How good can we approximate clique in this case?We have a clique $\frac{V(G)}{3}$ for free.
Does it help for clique if the vertices are partitioned into 3 cliques?
graph theory;graph algorithms