Rabern, L.


Hitting every large maximal clique with a stable set ★★

Author(s): King; Rabern

\begin{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)$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

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

Keywords: independent set; maximal clique

Syndicate content