# Paritioning a graph into clique and independent set

I am interested in the complexity of the following problems:

Input: an undirected graph $G = \langle V, E \rangle$

Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $I$ of equal size?

Query 2: are there a clique $C \subseteq V$ and an independent set $I \subseteq V$ whose sizes are at least $\frac{|V|}{4}$?

• Your restrictions seem quite artificial. Anyway, you might be interested in knowing that graphs whose vertex set can be partitioned into a clique and an independent set are known as split graphs. They are all chordal, and can be recognized in linear time.
– Juho
Jun 12 '16 at 17:23
• I removed the restriction. It seems the kind of restriction which is used for homework assignments, and homework assignments are off-topic here. See help center. You might want to check out our sister site Computer Science which has a boarder scope. Jun 12 '16 at 19:36