کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648575 | 1342418 | 2009 | 15 صفحه PDF | دانلود رایگان |
A clique-transversal of a graph GG is a subset of vertices that meets all the cliques of GG. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph GG is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of GG. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc (HCA) graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect HCA graphs.
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3485–3499