The clique-perfectness and clique-coloring of outer-planar graphs

A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. An open problem concerning clique-perfect graphs is to find all minimal forbidden induced subgraphs of clique-perfect graphs. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G and denoted by χC(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi _{C}(G)$$\end{document}. In this paper, we first find a class of minimal non-clique-perfect graphs and characterize the clique-perfectness of outer-planar graphs. Secondly, we present a linear time algorithm for the optimal clique-coloring of an outer-planar graph G.