How hard is this graph problem?
algorithm, graph
Solution
The decision version of problem is NP-Complete for general graphs: http://users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf and is applicable not just for triangles.
Of course, that still does not help resolve the question for the search version of 3-colourable graphs and triangle freeness (the decision version is trivially in P).
Problem
I have a problem to solve for a social-networks application, and it sounds hard: I'm not sure if its NP-complete or not. It smells like it might be NP-complete, but I don't have a good sense for these things. In any case, an algorithm would be much better news for me. Anyhow, the input is some graph, and what I want to do is partition the nodes into two sets so that neither set contains a triangle. If it helps, I know this particular graph is 3-colorable, though I don't actually know a coloring. Heuristically, a "greedy" algorithm seems to converge quickly: I just look for triangles in either side of the partition, and break them when I find them.