On hitting all maximum cliques with an independent set

Hitting all maximum cliques with a stabl

Hitting all maximum cliques with a stable set using lopsided independent transversals

✍ Andrew D. King 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

Rabern recently proved that any graph with ≥ 3 4 ( +1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with > 2 3 ( +1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding a