A linear-time algorithm for clique-coloring planar graphs

Abstract A clique of a graph G is a set of pairwise adjacent vertices of G . A clique-coloring of G is an assignment of colors to the vertices of G such that no inclusion-wise maximal clique of size at least 2 is monochromatic. Mohar and Skrekovski proved that planar graphs are 3-clique-colorable (Electr. J. Combin. 6 (1999), #R26). In this paper we present a linear time algorithm for 3-clique-coloring planar graphs by giving a new proof that planar graphs are 3-clique-colorable.