Partition into cliques for cubic graphs: Planar case, complexity and approximation

AbstractGiven a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V1,V2,…,Vk such that the subgraph induced by each part Vi is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time 54-approximation algorithm for finding clique partitions in maximum degree three graphs