A note on a Caro-Wei bound for the bipartite independence number in graphs

Shimon Kogan

A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t,t}$ in the bipartite complement of $G$. Given an $n\times n$ bipartite graph $G$, let $\beta (G)$ be the largest $k$ f…