King, Andrew D.


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

Syndicate content