{"id":"arxiv/2608.25233","url":"https://arxiv.org/abs/2608.25233","tags":["math.CO"],"score":0,"title":"Clique decompositions and covers for large graphs","domain":"math.CO","source":"arxiv","authors":["Wentao Zhang"],"reviews":0,"subject":"math.CO","summary":"In 1966, Erdős, Goodman, and Pó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ős suggested the following strengthening: every $n$-vertex graph $G$ admits an edge decomposition into cliques with total cost at most $\\lfloor \\frac{n^2}{4}\\rfloor$, where each $i$-clique has cost $i-1$. There is another generalization conjectured by Dau, Milenkovic and Puleo: for every $t\\ge4$, every $n$-vertex graph $G$ admits a cover of its $t$-cliques using at most…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}