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. Journal articles
  4. Partitioning cographs into cliques and stable sets
 
Loading...
Thumbnail Image
research article

Partitioning cographs into cliques and stable sets

Demange, Marc
•
Ekim, Tinaz  
•
de Werra, Dominique  
2005
Discrete Optimization

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case where k=p in \cite{tidosplit} where some upper and lower bounds on the optimal value minimizing k are also presented. We focus on cographs and devise some efficient algorithms for solving (p,k)-coloring problems and cocoloring problems in O(n^2+nm) time and O(n^{3/2}) time respectively. We also give an algorithm for finding the maximum induced (p,k)-colorable subgraph. In addition to this, we present characterizations of (2,1)- and (2,2)-colorable cographs by forbidden configurations.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.disopt.2005.03.003
Author(s)
Demange, Marc
•
Ekim, Tinaz  
•
de Werra, Dominique  
Date Issued

2005

Published in
Discrete Optimization
Volume

2

Issue

2

Start page

145

End page

153

Subjects

(p

•

k)-coloring

•

cocoloring

•

split-coloring

•

cographs.

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
October 21, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/218177
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