Polar cographs

EKİM T., Mahadev N., de Werra D.

Electronic Notes in Discrete Mathematics, cilt.28, ss.317-323, 2007 (Scopus)

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 28
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1016/j.endm.2007.01.045
  • Dergi Adı: Electronic Notes in Discrete Mathematics
  • Derginin Tarandığı İndeksler: Scopus
  • Sayfa Sayıları: ss.317-323
  • Anahtar Kelimeler: cographs, polar graphs, split graphs, threshold graphs
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

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. © 2007 Elsevier B.V. All rights reserved.