For every integer r≥ 3 and every finite graph F satisfying chi(F)=r and operatornametw(F)≥ r, there exist constants c_F>0 and n_0(F) such that, for every integer n≥ n_0(F), operatornameex(n,K_r,F)≥ c_F n^r-1, where operatornameex(n,K_r,F) denotes the maximum number of copies of K_r in an n-vertex F-free graph.

Gao–Wu–Xue treewidth conjecture for generalized Turán problems

For every integer $r\ge 3$ and every finite graph $F$ satisfying $\chi(F)=r$ and $\operatorname{tw}(F)\ge r$ , there exist constants $c_F>0$ and $n_0(F)$ such that, for every integer $n\ge n_0(F)$ , $\operatorname{ex}(n,K_r,F)\ge c_F n^{r-1}$ , where $\operatorname{ex}(n,K_r,F)$ denotes the maximum number of copies of $K_r$ in an $n$ -vertex $F$ -free graph.

References

Primary source

arXiv

Additional references

Counterexamples to a treewidth conjecture on generalized Turán problems — arXiv

extremal-graph-theory generalized-turn-problems

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unrefereed preprint claims a counterexample that makes the conjecture false in every relevant chromatic range.

The Gao–Wu–Xue conjecture concerns treewidth conditions in generalized Turán problems. The latest preprint claims a uniform counterexample, rather than resolving only an isolated case.

August 24, 2026 counterexample

On August 24, 2026, Counterexamples to a treewidth conjecture on generalized Turán problems claimed that, with $F_r=K_{r-3}\vee H$ ,

n^{r-1}e^{-O(\sqrt{\log n})}\le\operatorname{ex}(n,K_r,F_r)=o(n^{r-1}).

This gives a negative answer to the conjecture for every chromatic threshold. The construction and asymptotic bounds are from an unrefereed preprint and remain unverified.

Current status (as of August 2026): The conjecture is claimed false for every chromatic threshold by the stated preprint, but its counterexample and bounds have not been independently verified.

Sources

No solutions have been posted yet.