Complexity and algorithms for recognizing polar and monopolar graphs

Polar and monopolar graphs are natural generalizations of bipartite and split graphs. A graph G=(V,E)G=(V,E) is polar if its vertex set admits a partition V=A∪BV=A∪B such that A induces a complete multipartite graph and B the complement of a complete multipartite graph. If A is a stable set then G is called monopolar.This paper presents some sharp contrasts in the complexity of the recognition problem for monopolar graphs and for polar graphs. Among others we show that this problem is NP-complete for triangle-free planar graphs of maximum degree three, and is polynomially solvable on hole-free planar, chair-free planar and maximal planar graphs. We give a number of well-studied graph classes GG together with a relatively small subclass H⊂GH⊂G such that recognizing monopolar graphs in GG is polynomial while recognizing polar graphs in HH is NP-complete. Examples of such classes include the class of hole-free graphs GG and its tiny subclass of {2K2,C5}{2K2,C5}-free co-planar graphs HH, and the class of chair-free graphs GG and its tiny subclass of 3K13K1-free co-planar graphs HH. Our new NP-completeness results cover very restricted graph classes and sharpen known results, and the new positive results extend nearly all known results for monopolar recognition.