Non-bipartite spectral extremal graphs forbidding a three-chromatic color-critical graph
A graph is color-critical if it contains at least one color-critical edge. For every fixed three-chromatic color-critical graph $H$, we determine the maximum spectral radius of an $n$-vertex non-bipartite $H$-free graph and characterize the unique extremal graph for all sufficiently large $n$. The extremal graph belongs to one of three graph families: $J_n(s,t)$, $\mathrm{ST}_2(n-1)$ or $L_n(s,t)$. Explicit conditions on $H$ determine the family and its exact parameters. This paper generalizes the results for books and theta graphs to all three-chromatic color-critical graphs. Furthermore, an three-chromatic example demonstrates that spectral extremal graphs are not necessarily edge-extremal, disproving a conjecture of Fang and Lin [J. Algebraic Combin., 2026].
Authors
- Cunxiang Duan (ORCID: https://orcid.org/0000-0003-2571-0212)
- Attila Sali (ORCID: https://orcid.org/0000-0002-4837-6360)
- Ligong Wang
- Bo Dong
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24131
- Primary Topic
- Graph theory and applications
- Type
- preprint