Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Polar cographs
 
report

Polar cographs

Ekim, Tinaz  
•
Mahadev, N.V.R.
•
de Werra, Dominique  
2005

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. 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 (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).\ Recognizing a polar graph is known to be NP-complete. So these graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs and we derive a recognition algorithm in time O(nlogn). Besides, we give a polynomial time algorithm for finding a largest polar induced subgraph in cographs. We examine also the monopolar cographs which are the (s,k)-polar cographs where min (s,k)<= 1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

PolarCographs.pdf

Access type

openaccess

Size

134.21 KB

Format

Adobe PDF

Checksum (MD5)

520104fefe91018605549e7b627713b7

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés