A counterexample to the Fang--Lin conjecture: Edge and spectral extremality diverge near a Turán graph
Fang and Lin [J. Algebraic Combin. 63 (2026), Art.~58] asked whether, whenever $F$ is edge-color-critical with $χ(F)=r+1$, every non-$r$-partite, $F$-free graph of maximum adjacency spectral radius must also maximize the number of edges. We give a negative answer. Let $F=K_1\veeμ(K_3)$, where $μ(K_3)$ is the Mycielskian of a triangle. This graph is edge-color-critical with $χ(F)=5$. We prove that $\SPEX_{5}(n,F)\cap\EX_{5}(n,F)=\varnothing$ for all sufficiently large $n$. Thus no graph can simultaneously maximize both the edge count and the spectral radius.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.37208
curl -X POST /api/v1/records/arxiv/2609.37208/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.37208/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'