Let t_k-1(n) denote the maximum number of edges in a K_k-1-free graph on n vertices, and let tau_k(G) be the minimum size of a vertex set meeting every copy of K_k in G. For a balanced partition V_1 cup…cup V_k-1 of [n], assume |V_1|≥…≥|V_k-1|. Xiao and Katona's conjecture. For fixed integers k≥4 (and as stated in the source, s>t≥1), every graph G on n vertices with t_k-1(n)+1 edges and tau_k(G)≥2 contains at least (|V_1|+|V_2|-2)∏_i=3^k-1|V_i| copies of K_k. The paper states that it gives a counterexample to one Xiao–Katona conjecture and proves a modified version, so this original conjecture is refuted.

Xiao and Katona's clique-covering conjecture

Let $t_{k-1}(n)$ denote the maximum number of edges in a $K_{k-1}$ -free graph on $n$ vertices, and let $\tau_k(G)$ be the minimum size of a vertex set meeting every copy of $K_k$ in $G$ . For a balanced partition $V_1\cup\cdots\cup V_{k-1}$ of $[n]$ , assume $|V_1|\geq\cdots\geq|V_{k-1}|$ . Xiao and Katona's conjecture. For fixed integers $k\geq4$ (and as stated in the source, $s>t\geq1$ ), every graph $G$ on $n$ vertices with $t_{k-1}(n)+1$ edges and $\tau_k(G)\geq2$ contains at least

\left(|V_1|+|V_2|-2\right)\prod_{i=3}^{k-1}|V_i|

copies of $K_k$ . The paper states that it gives a counterexample to one Xiao–Katona conjecture and proves a modified version, so this original conjecture is refuted.

Xiao and Katona conjectured that graphs just above the Turán threshold, with no single vertex meeting every $K_k$ , must contain at least the number of $K_k$ copies given by the balanced-partition construction.

Claimed verification in a later arXiv version (date not stated)

Theorem 2 of the later paper asserts that, for sufficiently large $n$ , every graph in the conjecture has at least $(|V_1|+|V_2|-2)\prod_{i=3}^{k-1}|V_i|$ copies of $K_k$ , identifying this as a verification of the Xiao–Katona conjecture. The same paper’s modified result concerns a different conjecture; the retrieved source reports no counterexample to the stated clique-covering conjecture. This theorem remains unverified in this scan.

Current status (as of September 2026): The conjecture is claimed proved in its intended sufficiently-large- $n$ form, while independent verification and any treatment of exceptional small $n$ are not recorded here.

Xiao and Katona's clique-covering conjecture

Primary source

Progress summary

Solutions 0