Clique-transversal sets and clique-coloring in planar graphs

Let G=(V,E)G=(V,E) be a graph. A clique-transversal set  DD is a subset of vertices of GG such that DD meets all cliques of GG, where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number  , denoted by τC(G)τC(G), of GG is the cardinality of a minimum clique-transversal set in GG. A kk-clique-coloring   of GG is a kk-coloring of its vertices such that no clique is monochromatic. All planar graphs have been proved to be 3-clique-colorable by Mohar and Škrekovski [B. Mohar, R. Škrekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Combin. 6 (1999) #R26]. Erdős et al. [P. Erdős, T. Gallai, Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math. 108 (1992) 279–289] proposed to find sharp estimates on τC(G)τC(G) for planar graphs. In this paper we first show that every outerplanar graph GG of order n(≥2) has τC(G)≤3n/5τC(G)≤3n/5 and the bound is tight. Secondly, we prove that every claw-free planar graph different from an odd cycle is 22-clique-colorable and we present a polynomial-time algorithm to find the 22-clique-coloring. As a by-product of the result, we obtain a tight upper bound on the clique-transversal number for claw-free planar graphs.