Infoscience

Report

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).
Recognizing a polar graph is known to be NP-complete. So these graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs and we derive a recognition algorithm in time O(nlogn). Besides, we give a polynomial time algorithm for finding a largest polar induced subgraph in cographs. We examine also the monopolar cographs which are the (s,k)-polar cographs where min (s,k)<= 1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.

Related material