Dense minors of graphs with independence number two

Abstract

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 \left(\genfrac{}{}{0ex}{}{|V(H)|}{2}\right)-o(n^2)$$ edges.

Cited by in corpus (1)

• Biclique immersions in graphs with independence number 2