Finding the largest 3-clique-free induced subgraph

Consider this problem:

Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:

• $G'$ is an induced subgraph of $G$

• $G'$ has no 3-cliques

• $|V'|$ is maximal

So the least number of vertices must be eliminated from $G$ so that 3-cliques are eliminated.

An equivalent problem would be to find a 2-coloring for $G$ such that if $(v_1, v_2, v_3) \in V$ and $((v_1, v_2), (v_2, v_3), (v_3, v_1)) \in V$,

-
$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$

-
The (absolute) difference between the number of nodes with color 1 and the number of nodes with color 2 is maximal.

Can anyone think of a polynomial-time algorithm to solve one of these problems?

Both definitions leave your problem NP-hard, and have been answered on cstheory.

-
Interpretation 1, where you require the largest triangle free sub-graph, is NP-Hard and has been answered here.

-
Intepretation 2, where you need a partition such that both the induced sub-graphs are triangle free, has been answered here.

Note that the answers I linked to are for general $H$-freeness and are a class of $NP$-Hard problems.

StackExchange Computer Science Q#11518, answer score: 5