A linear-time algorithm for clique-coloring planar graphs

摘要

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. (C) 2019 Elsevier B.V. All rights reserved.