Unbalanced Turán and spectral Turán problems with prescribed large maximum degree
Abstract
Classical Turán theory shows that, without additional constraints, the extremal structure of F-free graphs is governed by the chromatic number of F and is asymptotically the balanced Turán graph. We investigate how prescribing a large maximum degree changes this picture and leads to an unbalanced Turán problem. Let F be a graph with χ(F)=r+1≥3, and let ⌈(r−1)n/r⌉≤Δ≤ n−1. We study the maximum number of edges and adjacency spectral radius of an n-vertex F-free graph with maximum degree exactly Δ. For F=Kr+1, the unbalanced r-partite graph Sn,Δ(r)=(n−Δ)K1∨ T(Δ,r−1) is the unique maximizer of both quantities. Let a(F) be the minimum size of an independent set I such that χ(F−I)≤ r. If a(F)=1, we prove edge and spectral stability with respect to Sn,Δ(r). If a(F)>1, the extremal values are t(n,r)+o(n2) and ρ(T(n,r))+o(n), respectively, and every extremal graph differs from T(n,r) in o(n2) edges, uniformly all ⌈(r−1)n/r⌉≤Δ≤ n−1. We further establish a general spectral transfer principle: for finite forbidden families, a decomposition-family bound of order O(n1+s) yields a spectral bound with error O(ns) for 0≤ s<1.
Related
- Unbalanced spectral Turán problem for color-critical graphs with prescribed large maximum degree
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- The maximum spectral radius of connected graphs with prescribed order and size
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
BibTeX
@misc{liu2026unbalanced,
title = {{Unbalanced Turán and spectral Turán problems with prescribed large maximum degree}},
author = {Chang Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.26634},
eprint = {2608.26634},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26634},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Unbalanced Turán and spectral Turán problems with prescribed large maximum degree
AU - Chang Liu
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2608.26634
UR - https://arxiv.org/abs/2608.26634
AB - Classical Turán theory shows that, without additional constraints, the extremal structure of F-free graphs is governed by the chromatic number of F and is asymptotically the balanced Turán graph. We investigate how prescribing a large maximum degree changes this picture and leads to an unbalanced Turán problem. Let F be a graph with χ(F)=r+1≥3, and let ⌈(r−1)n/r⌉≤Δ≤ n−1. We study the maximum number of edges and adjacency spectral radius of an n-vertex F-free graph with maximum degree exactly Δ. For F=K_r+1, the unbalanced r-partite graph S_n,Δ^(r)=(n−Δ)K_1∨ T(Δ,r−1) is the unique maximizer of both quantities. Let a(F) be the minimum size of an independent set I such that χ(F−I)≤ r. If a(F)=1, we prove edge and spectral stability with respect to S_n,Δ^(r). If a(F)>1, the extremal values are t(n,r)+o(n^2) and ρ(T(n,r))+o(n), respectively, and every extremal graph differs from T(n,r) in o(n^2) edges, uniformly all ⌈(r−1)n/r⌉≤Δ≤ n−1. We further establish a general spectral transfer principle: for finite forbidden families, a decomposition-family bound of order O(n^1+s) yields a spectral bound with error O(n^s) for 0≤ s<1.
ER -