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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-25 Page: https://delphi.science/r/arxiv/2608.25233 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…