Regarding two conjectures on clique and biclique partitions

Dhruv Rohatgi; John C. Urschel; Jake Wellens

paper

Regarding two conjectures on clique and biclique partitions

arXiv:2005.02529

Abstract

For a graph $G$ , let $c p (G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $b p_{k} (G)$ denote the minimum number of bicliques (i.e. complete bipartite subgraphs of $G$ ) needed to cover each edge of $G$ exactly $k$ times. We consider two conjectures -- one regarding the maximum possible value of $c p (G) + c p (G)$ (due to de Caen, Erdős, Pullman and Wormald) and the other regarding $b p_{k} (K_{n})$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $max_{G} c p (G) + c p (G)$ , and we prove an asymptotic version of the second, showing that $b p_{k} (K_{n}) = (1 + o (1)) n$ .