2023/10/20 by Yanbo Zhang, Yaojun Chen, Zhang, Yanbo +1 · 1 citation
Computer Science · Mathematics · #05C55 #05D10 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.13204
openalex publication_date 2023/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two graphs G1 and G2, the Ramsey number r(G1,G2) refers to the smallest positive integer N such that any graph G with N vertices contains G1 as a subgraph, or the complement of G contains G2 as a subgraph. A connected graph H is said to be p-good if r(Kp,H)=(p-1)(|H|-1)+1. A generalized fan, denoted as K1+nH, is formed by the disjoint union of n copies of H along with an additional vertex that is connected to each vertex of nH. Recently Chung and Lin proved that K1+nH is p-good for n≥ cpℓ/|H|, where c≈ 52.456 and ℓ=r(Kp,H). They also posed the question of improving the lower bound of n further so that K1+nH remains p-good. In this paper, we present three different methods to improve the range of n. First, we apply the Andrásfai-Erdős-Sós theorem to reduce c from 52.456 to 3. Second, we utilize the approach established by Chen and Zhang to achieve a further reduction of c to 2. Lastly, we employ a new method to bring c down to 1. In addition, when K1+nH forms a fan graph Fn, we can further obtain a slightly more refined bound of n.