Journal
JOURNAL OF GRAPH THEORY
Volume 67, Issue 4, Pages 300-305Publisher
WILEY
DOI: 10.1002/jgt.20532
Keywords
maximum clique; stable set; graph coloring; independent transversal; independent system of representatives
Categories
Funding
- NSERC
Ask authors/readers for more resources
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. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 67: 300-305, 2011
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available