Testing whether a given graph contains a balanced skew partition is also NP - complete in arbitrary graphs .
Testing whether a given graph contains a balanced skew partition may be solved in polynomial time in perfect graphs .
Testing whether a given graph contains a balanced skew partition is also NP - complete in arbitrary graphs , but may be solved in polynomial time in perfect graphs .