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

Zhicheng Gao, Brendan D. McKay, Reza Naserasr, Brett Stevens

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)211-228
    Number of pages18
    JournalAustralasian Journal of Combinatorics
    Issue number2
    Publication statusPublished - 2016


    Dive into the research topics of 'Bipartite edge partitions and the former Alon-Saks-Seymour conjecture'. Together they form a unique fingerprint.

    Cite this