Geodesic
Regarding two conjectures on clique and biclique partitions
The electronic journal of combinatorics, Tome 28 (2021) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/9564
Classification : 05C70, 05C35, 05C69
Mots-clés : extremal problem, complementary graphs, clique covering number, clique partition number

Dhruv Rohatgi    ; John C. Urschel    ; Jake Wellens  1

1 MIT 
@article{10_37236_9564,
     author = {Dhruv Rohatgi and John C. Urschel and Jake Wellens},
     title = {Regarding two conjectures on clique and biclique partitions},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {4},
     doi = {10.37236/9564},
     zbl = {1486.05250},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9564/}
}
TY  - JOUR
AU  - Dhruv Rohatgi
AU  - John C. Urschel
AU  - Jake Wellens
TI  - Regarding two conjectures on clique and biclique partitions
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9564/
DO  - 10.37236/9564
ID  - 10_37236_9564
ER  - 
%0 Journal Article
%A Dhruv Rohatgi
%A John C. Urschel
%A Jake Wellens
%T Regarding two conjectures on clique and biclique partitions
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9564/
%R 10.37236/9564
%F 10_37236_9564
Dhruv Rohatgi; John C. Urschel; Jake Wellens. Regarding two conjectures on clique and biclique partitions. The electronic journal of combinatorics, Tome 28 (2021) no. 4. doi: 10.37236/9564

Cité par Sources :