The Dau–Milenkovic–Puleo $K_t$ clique cover conjecture for $t\ge 5$

A $K_t$ clique cover of a graph $G$ is a family of cliques such that every complete subgraph on $t$ vertices of $G$ is contained in some member of the family, and $\theta_{K_t}(G)$ is the minimum size of such a family. Erdős, Goodman, and Pósa (1966) proved that $\theta_{K_2}(G)\le\lfloor n^2/4\rfloor$ for every $n$-vertex graph, with equality only for the balanced complete bipartite (Turán) graph. Dau, Milenkovic, and Puleo (2020) proved the analogous statement for $t=3$ and conjectured that for every $t$ the Turán graph $T(n,t)$ is the unique extremal graph: $\theta_{K_t}(G)\le\theta_{K_t}(T(n,t))$, with equality if and only if $G\cong T(n,t)$. The cases $t\le 4$ are now settled ($t=4$ by Chen, He, and Xie, 2025), an asymptotic version is known for every fixed $t\ge 2$ (Balogh, He, Krueger, Nguyen, and Wigal, 2024), and a 2026 preprint of Zhang settles the exact statement for all sufficiently large $n$ with non-explicit threshold. The exact conjecture for $t\ge 5$ — in particular for all $n\ge t$, and concretely for the small-to-moderate $n$ range below any large-$n$ threshold — remains open. The problem asks for a proof or an explicit counterexample.

Background

A clique of a graph is a set of pairwise adjacent vertices, and $K_t$ denotes the complete graph on $t$ vertices. For an integer $t\ge 1$, a $K_t$ clique cover of a graph $G$ is a collection of cliques of $G$ such that every copy of $K_t$ contained in $G$ (every $t$-clique) lies within at least one clique of the collection; $\theta_{K_t}(G)$, also written $\mathrm{CC}^t(G)$, is the minimum number of cliques in such a cover. For $t=2$ this is the classical edge clique cover number, which equals the intersection number of a graph (the minimum size of a ground set on which $G$ can be represented as an intersection graph of subsets); for $t=1$ it is the minimum number of cliques covering all vertices, which is at most $n$ with equality exactly for edgeless graphs.

A foundational result of Erdős, Goodman, and Pósa (1966) states that every $n$-vertex graph $G$ satisfies $\theta_{K_2}(G)\le\lfloor n^2/4\rfloor$, with equality if and only if $G$ is the balanced complete bipartite graph. This balanced complete bipartite graph is the Turán graph $T(n,2)$: for general $k$, the Turán graph $T(n,k)$ is the complete $k$-partite graph on $n$ vertices whose part sizes differ by at most one, i.e. the extremal $K_{k+1}$-free graph in Turán's theorem.

Dau, Milenkovic, and Puleo (2020) extended the Erdős–Goodman–Pósa theorem to $t=3$: every $n$-vertex graph satisfies $\theta_{K_3}(G)\le\theta_{K_3}(T(n,3))=\lfloor n/3\rfloor\lfloor(n+1)/3\rfloor\lfloor(n+2)/3\rfloor$, with equality (for $n\ge 3$) only for $G\cong T(n,3)$. Here $\theta_{K_t}(T(n,t))$ equals the number of $t$-cliques in $T(n,t)$, namely $\prod_{j=0}^{t-1}\lfloor(n+j)/t\rfloor$, because the largest cliques of $T(n,t)$ have exactly $t$ vertices, so every $t$-clique of $T(n,t)$ (a transversal of the $t$ partite classes) must itself appear in any $K_t$ clique cover. They posed the general conjecture that $T(n,t)$ is the unique extremal graph for the $K_t$ clique cover problem for every $t$: for all positive integers $n$ and $t$, every $n$-vertex graph $G$ satisfies $\theta_{K_t}(G)\le\theta_{K_t}(T(n,t))$, with equality if and only if $G\cong T(n,t)$. Their proof for $t=3$ is an induction on $n$ that removes a minimum-degree vertex and bounds the cover cost of the $t$-cliques containing it via a greedy clique partition of the neighborhood; they noted an explicit obstacle to extending it: the number of configuration types of $K_t$ across the parts of such a partition grows rapidly with $t$, so the case analysis becomes intractable for $t\ge 4$.

Subsequent work has substantially advanced — but not completed — the conjecture. Balogh, He, Krueger, Nguyen, and Wigal (2024) proved an asymptotic version: for every fixed $t\ge 2$, every $n$-vertex graph satisfies $\theta_{K_t}(G)\le(1+o(1))\theta_{K_t}(T(n,t))$ as $n\to\infty$, along with fractional relaxations, using Zykov symmetrization (an operation that replaces a vertex by a twin of another, non-adjacent vertex, gradually driving the graph toward a complete multipartite structure), the Frankl–Rödl nibble method (a randomized technique that covers a small fraction of the remaining objects in each of many independent rounds, yielding near-perfect coverings), and the Szemerédi Regularity Lemma (which partitions any large graph into a bounded number of vertex blocks whose pairwise interactions are quasirandom). Chen, He, and Xie (2025) confirmed the conjecture exactly for $t=4$: for every $n$-vertex graph $G$ with $n\ge 4$, $\theta_{K_4}(G)\le\theta_{K_4}(T(n,4))$, with equality if and only if $G\cong T(n,4)$; their proof combines an inductive framework on $n$, a generalized greedy partition, local adjustment operations, and clique-counting lemmas. Most recently, Zhang (2026, preprint) announced a proof of the conjecture for all sufficiently large $n$ for every fixed $t\ge 2$, with the same equality characterization, combining the graph removal lemma (any graph containing few copies of a fixed subgraph can be made free of them by deleting few edges), generalized Turán stability (a graph forbidding $K_{p}$ that has close to the maximum possible number of copies of $K_r$ must be structurally close to a Turán graph), and an explicit covering construction for graphs close to $T(n,t)$; the threshold $n_0(t)$ below which the statement is not covered is non-explicit, and the preprint is unrefereed. What no technique currently reaches is the exact statement for $t\ge 5$ at every $n\ge t$ — in particular the small-to-moderate range of $n$ for each $t\ge 5$. The question also connects to hypergraph covering theorems (Lehel's theorem on covering the hyperedges of a $t$-uniform hypergraph by hyperedges and hypercliques, i.e. complete sub-hypergraphs), where the analogous hypergraph extremal quantities are strictly larger than their graph counterparts, so hypergraph results do not transfer directly.

Problem Statement

Prove or refute the following statement, which is the surviving open core of the Dau–Milenkovic–Puleo $K_t$ clique cover conjecture after the settled cases $t\le 4$:

For every integer $t\ge 5$ and every integer $n\ge t$, every $n$-vertex graph $G$ satisfies

$$\theta_{K_t}(G)\ \le\ \theta_{K_t}\bigl(T(n,t)\bigr)\ =\ \prod_{j=0}^{t-1}\left\lfloor\frac{n+j}{t}\right\rfloor,$$

with equality if and only if $G\cong T(n,t)$.

The claim is the exact statement, required for all $n\ge t$ (in particular including the small-to-moderate $n$ range that asymptotic results and large-$n$ theorems with non-explicit thresholds do not cover). A complete proof must establish the inequality for every $t\ge 5$ and $n\ge t$ and characterize the equality cases; a disproof consists of an explicit graph $G$ on $n\ge t\ge 5$ vertices with $\theta_{K_t}(G)>\theta_{K_t}(T(n,t))$, or with $\theta_{K_t}(G)=\theta_{K_t}(T(n,t))$ but $G\not\cong T(n,t)$.

References

1. Hoang Dau, Olgica Milenkovic, Gregory J. Puleo, "On the Triangle Clique Cover and $K_t$ Clique Cover Problems", Discrete Mathematics 343(1):111627 (2020), DOI 10.1016/j.disc.2019.111627; arXiv:1709.01590, https://arxiv.org/abs/1709.01590
2. Paul Erdős, A. W. Goodman, Louis Pósa, "The Representation of a Graph by Set Intersections", Canadian Journal of Mathematics 18 (1966) 106–112, DOI 10.4153/cjm-1966-014-3, https://doi.org/10.4153/cjm-1966-014-3
3. József Balogh, Jialin He, Robert A. Krueger, The Nguyen, Michael C. Wigal, "Clique covers and decompositions of cliques of graphs", arXiv:2412.05522 (2024), https://arxiv.org/abs/2412.05522
4. Yihan Chen, Jialin He, Tianying Xie, "On the $4$-clique cover number of graphs", arXiv:2506.10478 (2025), https://arxiv.org/abs/2506.10478
5. Wentao Zhang, "Clique decompositions and covers for large graphs", arXiv:2608.25233 (2026), https://arxiv.org/abs/2608.25233