کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420614 | 683961 | 2008 | 25 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs](/preview/png/420614.png)
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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.
Journal: Discrete Applied Mathematics - Volume 156, Issue 7, 1 April 2008, Pages 1058–1082