Clique-transversal sets and clique-coloring in planar graphs

• DOI: 10.1016/j.ejc.2013.08.003
• Publication Date: 2013-09-19T06:01:18Z
• Authors: Erfang Shan; Zuosong Liang; Liying Kang
• Keywords: Clique-sum; Split graph; Clique graph; Treewidth; Induced subgraph

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