| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652853 | Electronic Notes in Discrete Mathematics | 2007 | 7 Pages |
Abstract
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 and B a disjoint union of at most k cliques. Recognizing a polar graph is known to be NP-complete. Here we consider the class of polar graphs which are also cographs. We provide polynomial time algorithms and forbidden subgraphs characterizations for problems related to polar cographs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
