论文标题
关于集团和比克利克分区的两个猜想
Regarding two conjectures on clique and biclique partitions
论文作者
论文摘要
对于图$ g $，让$ cp（g）$表示覆盖$ g $的边缘所需的最低列数量。同样，令$ bp_k（g）$表示覆盖$ g $ agy $ k $ k $ times的每个边缘所需的最小双晶（即完整的两部分子图）。我们考虑两种猜想 - 一个关于$ CP（g） + CP（\ edimelline {g}）$的最大可能值（由于de Caen，Erdős，Pullman和Wormald），另一个关于$ BP_K（K_N）$（由于De Caen，Gregory和Pritikin）。我们反驳了第一个，在$ \ max_g cp（g） + cp（\ overline {g}）$上获得了改进的上限和上限，我们证明了第二个的渐近版本，表明$ bp_k（k_n）=（1 + o（1 + o（1 + o（1））n $。
For a graph $G$, let $cp(G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $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 $cp(G) + cp(\overline{G})$ (due to de Caen, Erdős, Pullman and Wormald) and the other regarding $bp_k(K_n)$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $\max_G cp(G) + cp(\overline{G})$, and we prove an asymptotic version of the second, showing that $bp_k(K_n) = (1+o(1))n$.
