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

✍ Scribed by Andrew D. King

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 82 KB
• Volume: 67
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20532

✦ Synopsis

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 an independent transversal in a graph partitioned into vertex sets of unequal size.