Clique-transversal sets and clique-coloring in planar graphs

Let G = ( V , E ) be a graph. A clique-transversal set D is a subset of vertices of G such that D meets all cliques of G , 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 ) , of G is the cardinality of a minimum clique-transversal set in G . A k -clique-coloring of G is a k -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 ) for planar graphs. In this paper we first show that every outerplanar graph G of order n ( ≥ 2 ) has τ C ( G ) ≤ 3 n / 5 and the bound is tight. Secondly, we prove that every claw-free planar graph different from an odd cycle is 2 -clique-colorable and we present a polynomial-time algorithm to find the 2 -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.