6
$\begingroup$

It is well known that in a perfect graph, there exists a clique which intersects all maximum independent sets (stable set), as in the proof of weak perfect graph theorem. So I want to know is the stronger statement true: In a perfect graph, there exists a clique which intersects all maximal independent sets.

(A maximum indepedent set is the largest indepedent set. A maximal independent set is an indepedent set which not contained in any larger independent set.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

This stronger statement is not true. Consider $C_6$, which is bipartite and thus perfect. There are three maximal independent set of size two, but each clique intersects only two out of the three.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .