The Alon-Saks-Seymour conjecture is the refuted assertion that every finite simple graph whose edge set
can be partitioned into 
complete bipartite
subgraphs has chromatic number at most 
.
It was proposed by Alon, Saks, and Seymour (Huang and Sudakov 2012). In terms of
the biclique partition number 
, the conjectured inequality is
 |
The bicliques here need not be induced subgraphs. They may share vertices, but every graph edge must belong to exactly one part. A biclique cover allows repeated coverage of edges, and its minimum size is the bipartite dimension, a different parameter.
Huang and Sudakov (2012) disproved the conjecture. Their construction gives an infinite family of graphs with unbounded biclique partition number satisfying
 |
for an absolute constant 
. Thus the chromatic number
can grow superlinearly in the number of parts,
rather than obeying the proposed bound.
