For this question, you could have vertices be animals and edges between 
animals represent the fact that (at least) one would fight or eat the 
other if placed in the same habitat.

Then, find the minimal number of colors required to paint the vertices 
so no neighboring vertices have the same color.  Every animal with the 
same color can live together.

You could run 2-Color to see if you get lucky, but if not (and in the 
worst case two colors would not be enough) then the best known approaches
are exponential.