Partition into cliques for cubic graphs: Planar case, complexity and approximation ?
Given a graph G=(V,E) G = ( V , E ) and a positive integer k k , the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V V into k k disjoint subsets V1,V2,,Vk V 1 , V 2 ,  , V k such that the subgraph induced by each part Vi V i is a complete subgraph (clique) of G 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 5 4 -approximation algorithm for finding clique partitions in maximum degree three graphs.
partition into cliques approximation np-complete max snp-hard coloring cubic planar graphs