About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs (Q1084418)

The paper concerns the concept of a polar graph (other than that of F. Zítek). A polar graph is an ordered triple (G,A,B), where G is a graph and A, B are disjoint sets whose union is the vertex set of G and which have the property that B induces a subgraph of G, all of whose connected components are complete graphs, and A induces such a subgraph of the complement \(\bar G\) of G. Let each of the symbols \(\alpha\), \(\beta\) denote a positive integer or \(\infty\). If none of the connected components of the subgraph of \(\bar G\) induced by A has more than \(\alpha\) vertices and none of the connected components of the subgraph of G induced by B has more than \(\beta\) vertices, then it is written (G,A,B)\(\in (\alpha,\beta).\) The problem of recognizing whether a given polar graph (G,A,B) belongs to (\(\infty,\beta)\) is called the POLAR(\(\beta)\) problem; the analogous problem for (\(\infty,\infty)\) is called the POLAR problem. It is proved that POLAR(\(\beta)\) for all \(\beta >1\) and POLAR are both NP-complete.