2025/08/18 by Fang, Longfei, Lin, Huiqiu · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.12855
Fix a color-critical graph H with χ(H)=r+1≥ 3. Simonovits' chromatic critical edge theorem and Nikiforov's spectral chromatic critical edge theorem imply that Tn,r is the extremal graph with the maximum size and the maximum spectral radius over all H-free graphs of order n, respectively. Since Tn,r is r-partite, it is interesting to study the Turán number and the spectral Turán number of a color-critical graph H in non-r-partite graphs. Denote by \rm EXr+1(n,H) (resp. \rm SPEXr+1(n,H)) the family of n-vertex H-free non-r-partite graphs with the maximum size (resp. spectral radius). Brouwer showed that any graph in EXr+1(n,Kr+1) is of size e(Tn,r)-\lfloor(n)/(r)\rfloor+1 for n≥ 2r+1. Lin, Ning and Wu [Combin. Probab. Comput. 30 (2) (2021) 258--270], and Li and Peng [SIAM J. Discrete Math. 37 (2023) 2462--2485] characterized the unique graph in SPEXr+1(n,Kr+1) for r≥ 2. Particularly, the unique graph is of size e(Tn,r)-\lfloor(n)/(r)\rfloor+1. Thus SPEXr+1(n,Kr+1)⊆ EXr+1(n,Kr+1). It is natural to conjecture that \rm SPEXr+1(n,H)⊆ \rm EXr+1(n,H) for arbitrary color-critical graph H with χ(H)=r+1≥ 3. Fix q,r≥ 2 with even q, a theta graph θ(1,q,r) is obtained from internally disjoint paths of lengths 1,q,r, respectively by sharing a common pair of endpoints. In this paper, we prove that SPEX3(n,θ(1,q,r))⊆ EX3(n,θ(1,q,r)) for sufficiently large n. Furthermore, we determine all the graphs in SPEX3(n,θ(1,q,r)) and EX3(n,θ(1,q,r)), respectively.