Clique and anticlique partitions of graphs

Krzysztof Bryś , Zbigniew Lonc

Abstract

In the paper we prove that, for a fixed k, the problem of deciding whether a graph admits a partition of its vertex set into k-element cliques or anticliques (i.e. independent sets) is polynomial.
Author Krzysztof Bryś ZAK
Krzysztof Bryś,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc ZAK
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
Journal seriesDiscrete Mathematics, ISSN 0012-365X
Issue year1998
Vol185
No1–3
Pages41-49
DOIDOI:10.1016/S0012-365X(97)00181-7
URL http://www.sciencedirect.com/science/article/pii/S0012365X97001817
Score (nominal)20
Publication indicators WoS Impact Factor: 2006 = 0.347 (2) - 2007=0.501 (5)
Citation count*3 (2015-02-23)
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back