Large cliques and large independent sets: can they coexist?

Uriel Feige, Ilia Pauzner

For a graph $G$ and a parameter $k$, we call a vertex $k$-enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$, and we call it $k$-excluding ot…