Advertisement
Published in:
10-05-2019
The clique-perfectness and clique-coloring of outer-planar graphs
Published in: Journal of Combinatorial Optimization | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 \(\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.