A note on hitting maximum and maximal cliques with a stable set

2011/09/14 by Demetres Christofides, Christofides, Demetres, Katherine Edwards +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1109.3092

7 pages, two figures, accepted to J. Graph Theory

arxiv created 2012/05/28 · arxiv updated 2012/05/29

Abstract

It was recently proved that any graph satisfying ω> \frac 23(Δ+1) contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying ω≥ \frac 23(Δ+1) unless the graph is the strong product of K_ω/2 and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.

Related

• Combinatorial Properties of the Family of Maximum Stable Sets of a Graph
• A short proof that χ can be bounded ε away from Δ+1 towards ω
• The Intersection of All Maximum Stable Sets of a Tree and its Pendant Vertices
• Stability for maximal independent sets
• Interval greedoids and families of local maximum stable sets of graphs