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

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

2009-11-09

arxiv.org/abs/0911.1741v4

Computer Science

Discrete Mathematics

7 pages. v4: Correction to statement of Lemma 8 and clarified proof.

Scientific paper

10.1002/jgt.20532

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.

Affiliated with

Also associated with

No associations

Rating

Hitting all maximum cliques with a stable set using lopsided independent transversals 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 Hitting all maximum cliques with a stable set using lopsided independent transversals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting all maximum cliques with a stable set using lopsided independent transversals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660630