![](/files/happy5.png)
Alon-Saks-Seymour Conjecture (Solved)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ m $](/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png)
![$ \chi(G) \le m+1 $](/files/tex/0aefe0f752ac272776eec5c61c7d1a1822a3d224.png)
This conjecture may be viewed as a bipartite analogue of the Erdos-Faber-Lovasz Conjecture.
One very special case of this conjecture is the statement that a complete graph on vertices cannot be written as a disjoint union of fewer than
complete bipartite graphs (although it does have numerous such decompositions). This was proved by Graham and Pollak [GP] who used spectral techniques to establish the following stronger fact.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ p $](/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png)
![$ q $](/files/tex/0f3b87f25409a259a157fcac9808cafa54efa0c7.png)
![$ H_1,\ldots,H_k \subseteq G $](/files/tex/64d59ea9065a6abf5388129e1102361ca9ecb4fa.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H_i $](/files/tex/b5eebbb6562e3e98766f53decb43a78b1f076151.png)
![$ k \ge \max\{p,q\} $](/files/tex/62b52611966d5c9f70e4f131df8b05a7ff9a94fa.png)
Alternative proofs of the Graham-Pollak Theorem have been found by [P] and [T], and Alon, Brualdi, and Schader [ABS] resolved a conjecture of de Caen by proving that whenever is edge-colored so that each color class induces a complete bipartite graph, there is a spanning tree with one edge of each color. However, all of these results depend heavily on spectral tools. A proof of the general conjecture would appear to either require a vast generalization of these techniques, or a new combinatorial proof of the Graham-Pollak Theorem.
Bibliography
[ABS] N. Alon, R. A. Brualdi and B. L. Shader, Multicolored forests in bipartite decompositions of graphs, J. Combinatorial Theory Ser. B 53 (1991), 143-148.
[GP] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell Syst. Tech. J. 50 (1971), 2495-2519.
[P] G. W. Peck, A new proof of a theorem of Graham and Pol lak, Discrete Math. 49 (1984), 327-328.
[T] H. Tverberg, On the decomposition of Kn into complete bipartite graphs, J. Graph Theory 6 (1982), 493-494.
* indicates original appearance(s) of problem.
Solved!!
Hao Huang and Benny Sudakov have found a fascinating counterexample to this conjecture. Their paper can be found on the arxiv here