Home » Keyword index

maximal clique


Graph Theory

Hitting every large maximal clique with a stable set ★★

Author(s): King; Rabern

Conjecture   There is a universal constant $ \epsilon>0 $ such that every graph contains a stable set which intersects every maximal clique of size $ (1-\epsilon)(\Delta+1) $.

Conjecture   Every graph contains a stable set which intersects every maximal clique of size $ >\frac{2}{3}(\Delta+1) $.

Keywords: independent set; maximal clique

Posted by Andrew King
updated March 31st, 2011
add new comment
Syndicate content