Dense minors of graphs with independence number two

Motivated by Hadwiger's conjecture, we prove that every $n$-vertex graph $G$ with no independent set of size three contains an $\lceil n/2\rceil$-vertex simple minor $H$ with $0.98688 \cdot \binom{|V(H)|}{2} - o(n^2)$ edges.

No reviews yet.

No comments yet.