Information System on Graph Classes and their Inclusions
| Input: | A graph G in this class and an integer k. |
| Output: | True iff the vertices of G can be partitioned into two sets A,B of equal size (or |A|=|B|-1 if G has an odd number of vertices) such that there are at most k edges in G with one endpoint in A and the other endpoint in B. |
(G)-perfect
3-perfect