Bipartite edge partitions and the former Alon-Saks-Seymour conjecture

Abstract

A famous result of Graham and Pollak states that the complete graph with n vertices can be edge partitioned into n − 1, but no fewer, complete bipartite graphs. This result has led to the study of the relationship between the chromatic and biclique partition numbers of graphs. It has become even more exciting with recent connections to the clique versus stable set problem, communication protocols and constraint satisfaction and homomorphism problems. By defining an extended hypercube we construct a framework that provides much structural information regarding the relationship between these two parameters and a third, the induced bipartite edge partition number. Using this we show that the minimum counterexample to the former Alon-Saks-Seymour conjecture must have biclique partition number at least 10. Finally we identify a family of graphs to investigate for a smaller counterexample to the former Alon-Saks-Seymour conjecture.