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 maximalSo 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?
Finding the largest 3-clique-free induced subgraph
algorithms;graph theory;graphs;optimization
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.