2021/12/30 by Hei, Doudou, Hou, Xinmin, Liu, Boyuan
#05C35 #05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2112.14895
For graphs H and F with chromatic number χ(F)=k, we call H strictly F-Turán-good (or (H, F) strictly Turán-good) if the Turán graph Tk-1(n) is the unique F-free graph on n vertices containing the largest number of copies of H when n is large enough. Let F be a graph with chromatic number χ(F)≥ 3 and a color-critical edge and let P_ℓ be a path with ℓ vertices. Gerbner and Palmer (2020, arXiv:2006.03756) showed that (P3, F) is strictly Turán good if χ(H)≥ 4 and they conjectured that (a) this result is true when χ(F)=3, and, moreover, (b) (P_ℓ, Kk) is Turán-good for every pair of integers ℓ and k. In the present paper, we show that (H, F) is strictly Turán-good when H is a bipartite graph with matching number ν(H)=\lfloor (|V(H)|)/(2)\rfloor and χ(F)= 3, as a corollary, this result confirms the conjecture (a); we also prove that (P_ℓ, F) is strictly Turán-good for 2≤ℓ≤ 6 and χ(F)≥ 4, this also confirms the conjecture (b) for 2≤ℓ≤ 6 and k≥ 4.