For every integer k≥ 6 and every finite nonempty K_k-free graph G, the binding number satisfies operatornamebind(G)≤ k-2, where operatornamebind(G)=minfrac|N_G(S)||S|:varnothing≠ S⊆ V(G), N_G(S)≠ V(G) and N_G(S) is the set of vertices outside S adjacent to at least one vertex of S. The bound is sharp, as shown by complete (k-1)-partite graphs with equal nonempty parts.

Brandt conjecture on the binding number of K_k-free graphs

For every integer $k\ge 6$ and every finite nonempty $K_k$ -free graph $G$ , the binding number satisfies $\operatorname{bind}(G)\le k-2$ , where $\operatorname{bind}(G)=\min\left\{\frac{|N_G(S)|}{|S|}:\varnothing\ne S\subseteq V(G),\ N_G(S)\ne V(G)\right\}$ and $N_G(S)$ is the set of vertices outside $S$ adjacent to at least one vertex of $S$ . The bound is sharp, as shown by complete $(k-1)$ -partite graphs with equal nonempty parts.

References

arXiv

A sharp bound on the binding number of K_k-free graphs and the Brandt conjecture — arXiv — Jifu Lin, Heng Yang

extremal-graph-theory

Posted 3 hours ago · edited 2 hours ago

Progress summary

Refreshed 2 hours ago

Open · progress reported

A new unrefereed paper claims the conjectured threshold for clique-free graphs from six cliques onward, but the claim has not been independently checked.

The conjecture asks for a sharp binding-number threshold in graphs containing no $K_k$ .

Recent preprint

Jifu Lin and Heng Yang claim to prove the conjectured bound for $k\ge 6$ , establishing the base case $k=6$ and treating larger $k$ by induction. If correct, this settles that range, but the preprint has no independent mathematical assessment in the retrieved sources.

Current status (as of October 2026): A preprint claims the conjectured bound for all $k\ge 6$ , but the claim is unverified and the problem is not recorded as solved.

Sources

arxiv.org

No solutions have been posted yet.