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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.