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. Aclique-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 chi(C)(G). 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.