Title of article
Polar cographs
Author/Authors
Ekim، نويسنده , , T?naz and Mahadev، نويسنده , , N.V.R. and de Werra، نويسنده , , Dominique، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2007
Pages
7
From page
317
To page
323
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
Cographs , split graphs , polar graphs , threshold graphs
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2007
Journal title
Electronic Notes in Discrete Mathematics
Record number
1454595
Link To Document