Regarding two conjectures on clique and biclique partitions (Q2121747): Difference between revisions

Summary: For a graph \(G\), let \(\mathrm{cp}(G)\) denote the minimum number of cliques of \(G\) needed to cover the edges of \(G\) exactly once. Similarly, let \(\mathrm{bp}_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 \(\mathrm{cp}(G) + \mathrm{cp}(\overline{G})\) (due to \textit{D. de Caen} et al. [Combinatorica 6, 309--314 (1986; Zbl 0616.05042)]) and the other regarding \(\mathrm{bp}_k(K_n)\) (due to \textit{D. de Cean} et al. [Lect. Notes Pure Appl. Math. 139, 93--119 (1993; Zbl 0790.05064)]). We disprove the first, obtaining improved lower and upper bounds on \(\max_G \mathrm{cp}(G) + \mathrm{cp}(\overline{G})\), and we prove an asymptotic version of the second, showing that \(\mathrm{bp}_k(K_n) = (1+o(1))n\).