paper

Sharp bounds for covering with large cliques and independent sets

arXiv:2604.20962

Abstract

Let $n (k_{1}, k_{2})$ be the least integer $n$ such that there exists a graph on $n$ vertices in which every vertex is contained in both a clique of size $k_{1}$ and an independent set of size $k_{2}$ . Recently, Feige and Pauzner showed that $n (k, k) \geq 4 k - O (k^{\frac{2}{3}})$ , and conjectured that $n (k, k) = 4 k - 4$ . We prove this conjecture, and also establish the optimal lower bound in the more general case where $k_{1}$ and $k_{2}$ are arbitrary. We further consider the generalisation of the problem to $r$ -edge-coloured complete graphs in which every vertex is contained in a size- $k$ monochromatic clique of each colour, and obtain upper and lower bounds on the size of such graphs.

14 pages, 3 figures