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 :
بازگشت