Alon-Saks-Seymour Conjecture (1994)

Originator(s): N. Alon, M. Saks, P.D. Seymour

Conjecture/Question: Every union of $m$ pairwise edge-disjoint complete bipartite graphs is $(m+1)$-colorable.

Background/motivation: This statement is a bipartite analogue of the Erdos-Faber-Lov\'asz Conjecture. A special case of it would be the Graham-Pollak Theorem stating that the minimum number of complete bipartite subgraphs needed to decompose $K_n$ is $n-1$. Algebraic proofs of this theorem are known, but no purely combinatorial proofs are known.

Comments/Partial results: The conjecture has been shown to be FALSE. Huang-Sudakov [HS] constructed a family of counterexamples having a superlinear gap between the chromatic number and the biclique partition number. They posed a new conjecture that the union of $m$ edge-disjoint bicliques is $2^{(\log_2 m)^2}$-colorable and that this is sharp. The new conjecture is related to a conjecture in theoretical computer science about the complexity of a certain problem.

[GP] R.L. Graham and H.O. Pollak, On embedding graphs in squashed cubes. Graph theory and applications (Proc. Quadrennial Conf. on Graph Theory, Western Michigan Univ., Kalamazoo, Mich., 1972), Lecture Notes in Math. 303 (Springer, 1972), 99-110.
[HS] H. Huang and B. Sudakov, A counterexample to the Alon-Saks-Seymour conjecture and related problems, , Combinatorica, to appear.

Index Page; Glossary

Posted 04/06/05; Last update 09/13/11