Wentao Zhang

Clique decompositions and covers for large graphs

In 1966, Erd\H{o}s, Goodman, and P\'{o}sa showed that every $n$-vertex graph $G$ admits a cover of its edges using at most $\lfloor \frac{n^2}{4}\rfloor$ cliques, with tightness witnessed by the balanced complete bipartite graph. Erd\H{o}s suggested the following strengthening: every $n$-vertex graph $G$ admits an edge...