Polar cographs |
| |
| Institution: | 1. Institute of Mathematics - ROSE, Ecole Polytechnique Fédérale de Lausanne, CH-1015 Lausanne-Ecublens, Switzerland;2. Fitchburg State College, Department of Computer Science, USA |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
