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.
- View record in Web of Science
Record created on 2006-09-27, modified on 2016-08-08