Problem Statement
The bipartition number $\tau(G)$ of a graph $G$ is the smallest number of pairwise edge disjoint complete bipartite graphs whose union is $G$. The independence number $\alpha(G)$ is the size of the largest independent subset of $G$.
Is it true that, if $G$ is a random graph on $n$ vertices with edge probability $1/2$, then\[\tau(G)=n-\alpha(G)\]almost surely?
Is it true that, if $G$ is a random graph on $n$ vertices with edge probability $1/2$, then\[\tau(G)=n-\alpha(G)\]almost surely?
Categories:
Graph Theory
Progress
Alon [Al15] showed this is false: in fact almost surely $\tau(G) \leq n-\alpha(G)-1$. Alon, Bohman, and Huang [ABH17] proved that in fact there is some absolute constant $c>0$ such that almost surely\[\tau(G) \leq n-(1+c)\alpha(G).\]Source: erdosproblems.com/807 | Last verified: January 16, 2026