For every edge-color-critical graph F with chi(F)=r+1, and every positive integer n, let G_n,r(F) be the family of all n-vertex, F-free graphs that are not r-partite. The Fang–Lin conjecture asserts that every graph in G_n,r(F) having maximum adjacency spectral radius also has the maximum number of edges; equivalently, operatornameSPEX_r(n,F)⊆ operatornameEX_r(n,F). The cited preprint claims that this fails for F=K_1 veemu(K_3), for which chi(F)=5: for all sufficiently large n, no non-4-partite, F-free n-vertex graph simultaneously maximizes the edge count and the adjacency spectral radius, i.e. operatornameSPEX_4(n,F)cap operatornameEX_4(n,F)=varnothing.

Fang–Lin conjecture

For every edge-color-critical graph $F$ with $\chi(F)=r+1$ , and every positive integer $n$ , let $\mathcal{G}_{n,r}(F)$ be the family of all $n$ -vertex, $F$ -free graphs that are not $r$ -partite. The Fang–Lin conjecture asserts that every graph in $\mathcal{G}_{n,r}(F)$ having maximum adjacency spectral radius also has the maximum number of edges; equivalently, $\operatorname{SPEX}_{r}(n,F)\subseteq \operatorname{EX}_{r}(n,F)$ . The cited preprint claims that this fails for $F=K_1\vee\mu(K_3)$ , for which $\chi(F)=5$ : for all sufficiently large $n$ , no non- $4$ -partite, $F$ -free $n$ -vertex graph simultaneously maximizes the edge count and the adjacency spectral radius, i.e. $\operatorname{SPEX}_{4}(n,F)\cap\operatorname{EX}_{4}(n,F)=\varnothing$ .

References

Primary source

arXiv

Additional references

A counterexample to the Fang--Lin conjecture: Edge and spectral extremality diverge near a Turán graph — arXiv — Qi Wu, Yong Lu

extremal-graph-theory spectral-graph-theory

Posted 1 week ago · edited 1 week ago

Progress summary

Refreshed 1 week ago

Claimed solved

A recent unrefereed preprint claims a counterexample that disproves the Fang–Lin conjecture in sufficiently large dimensions, but the claim has not been independently verified.

The Fang–Lin conjecture proposes an equivalence between edge-extremal and spectral-radius-extremal objectives for forbidden-subgraph problems. The reported counterexample concerns $F=K_1\vee\mu(K_3)$ and non- $r$ -partite graphs.

September 2026 counterexample

Qi Wu and Yong Lu claim that, for $F=K_1\vee\mu(K_3)$ and all sufficiently large $n$ , the edge-maximizing and spectral-radius-maximizing non- $r$ -partite $F$ -free graphs are disjoint. This would refute the conjectured equivalence. A separate preprint gives related negative results in the linear-excess setting and conditional positive results under additional hypotheses.

Current status (as of September 2026): The conjecture is claimed disproved for the stated forbidden-graph family, but the unrefereed counterexample remains unverified; the full general scope is not settled.

Sources

No solutions have been posted yet.