pith. sign in

arxiv: 0911.1741 · v4 · pith:OBVG7UMYnew · submitted 2009-11-09 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords graphstablecliquesdeltaindependentmaximumomegacontains
0
0 comments X
read the original abstract

Rabern recently proved that any graph with omega >= (3/4)(Delta+1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with omega > (2/3)(Delta+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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.