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ś (FMIS / DAC)
Krzysztof Bryś,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc (FMIS / DAC)
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
Pages67-72
Book Fabrizio , Franciosa Paolo Giulio, Marchetti-Spaccamela Alberto (eds.): Graph-Theoretic Concepts in Computer Science, Lecture Notes In Computer Science, no. 1197, 1997, Springer Berlin Heidelberg, ISBN 978-3-540-62559-9, 978-3-540-68072-7
Keywords in EnglishAlgorithm Analysis and Problem Complexity, Combinatorics, Computation by Abstract Devices, Computer Graphics, data structures
URL http://link.springer.com/chapter/10.1007/3-540-62559-3_7
Score (nominal)3
Publication indicators WoS Citations = 0
Citation count*
Cite
Share Share

Get link to the record


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