Proof of Chvatal's conjecture on maximal stable sets and maximal cliques in graphs

摘要

Grillet established conditions on a partially ordered set under which each maximal antichain meets each maximal chain. Chvatal made a conjecture in terms of graphs that strengthens Grillet's theorem. The purpose of this paper is to prove this conjecture. (C) 2004 Elsevier Inc. All rights reserved.