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

Given a graph G=(V,E)G=(V,E) and a positive integer kk, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of VV into kk disjoint subsets V1,V2,…,VkV1,V2,…,Vk such that the subgraph induced by each part ViVi is a complete subgraph (clique) of GG. 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.