RECORD
Clique decompositions and covers for large graphs
Combinatorics · Submitted 25 Aug 2026
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We solve both conjectures for large $n$ and identify the equality cases.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 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 $\prod_{j=0}^{t-1}\left\lfloor\frac{n+j}{t}\right\rfloor$ cliques. Balogh, He, Krueger, Nguyen and Wigal proved asymptotic and fractional versions of these conjectures. We solve both conjectures for large $n$ and identify the equality cases. Our proof of Erd\H{o}s's conjecture combines linear programming duality and the spanning-forest polytope with a weighted stability form of Mantel's theorem, followed by explicit decomposition algorithms around an almost balanced bipartition. For the $t$-clique-cover conjecture, we combine graph removal lemma and generalized Tur\'an stability with an exact covering construction for graphs close to $T_{n,t}$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.02 | 0.03 | asserted 1.00 |
| s1 | Erd\H{o}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$. | background 0.98 | 0.02 | 0.03 | hedged possibility 0.52 |
| s2 | 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 $\prod_{j=0}^{t-1}\left\lfloor\frac{n+j}{t}\right\rfloor$ cliques. | background 0.99 | 0.03 | 0.03 | speculative 0.91 |
| s3 | Balogh, He, Krueger, Nguyen and Wigal proved asymptotic and fractional versions of these conjectures. | background 0.98 | 0.03 | 0.02 | asserted 1.00 |
| s4 | We solve both conjectures for large $n$ and identify the equality cases. | contribution 0.66 | 0.97 | 0.95 | asserted 1.00 |
| s5 | Our proof of Erd\H{o}s's conjecture combines linear programming duality and the spanning-forest polytope with a weighted stability form of Mantel's theorem, followed by explicit decomposition algorithms around an almost balanced bipartition. | method 0.99 | 0.96 | 0.07 | asserted 1.00 |
| s6 | For the $t$-clique-cover conjecture, we combine graph removal lemma and generalized Tur\'an stability with an exact covering construction for graphs close to $T_{n,t}$. | method 0.98 | 0.94 | 0.07 | asserted 0.98 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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 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 $\prod_{j=0}^{t-1}\left\lfloor\frac{n+j}{t}\right\rfloor$ cliques. Balogh, He, Krueger, Nguyen and Wigal proved asymptotic and fractional versions of these conjectures. We solve both conjectures for large $n$ and identify the equality cases. Our proof of Erd\H{o}s's conjecture combines linear programming duality and the spanning-forest polytope with a weighted stability form of Mantel's theorem, followed by explicit decomposition algorithms around an almost balanced bipartition. For the $t$-clique-cover conjecture, we combine graph removal lemma and generalized Tur\'an stability with an exact covering construction for graphs close to $T_{n,t}$.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 8 sentences without a confident label
Uses the method or tool of 1 paper
-
We use the same symmetrization operation as in [ref] to reduce \(G_0\) to a complete multipartite graph.
Clique covers and decompositions of cliques of graphs · Introduction · 1.00
Cites as support 1 paper
-
Results from [ref] suggest we can delete very few edges from \(G\) to get a subgraph \(G_0\) such that \(_t(G_0)\) only decreases a little from \(_t(G)\).
Clique covers and decompositions of cliques of graphs · Introduction · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.