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

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

2011-09-14

arxiv.org/abs/1109.3092v1

Computer Science

Discrete Mathematics

6 pages, two figures

Scientific paper

It was recently proved that any graph satisfying $\omega > \frac 23(\Delta+1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying $\omega \geq \frac 23(\Delta+1)$ unless the graph is the strong product of $K_{\omega/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.

Affiliated with

Also associated with

No associations

Rating

A note on hitting maximum and maximal cliques with a stable set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on hitting maximum and maximal cliques with a stable set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on hitting maximum and maximal cliques with a stable set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-569898