Search

For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) [6] shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 for all n ≥ 2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γ q on q 2 − 1 vertices without C 4 by using the Galois field F q , and then we prove that R ( C 4 , K 1 , ( q − 1 ) 2 + t ) = ( q − 1 ) 2 + q + t for q ≥ 4 is even and t = 1 , 0 , − 2 , and R ( C 4 , K 1 , q ( q − 1 ) − t ) = q 2 − t for q ≥ 5 is odd and t = 2 , 4 , . . . , 2 ⌈ q 4 ⌉ . [ABSTRACT FROM AUTHOR]

For k given graphs H 1 , ... , H k , k ≥ 2 , the k -color Ramsey number, denoted by R (H 1 , ... , H k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of H i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m , K 1 , n a star of order n + 1 and W n a wheel of order n + 1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k + 1) -color Ramsey number R (C 4 , ... , C 4 , K 1 , n) for some special n , which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R (C 4 , ... , C 4 , K 1 , n) in terms of n and k , which extends the classical result of Burr et al. (1989). Moreover, we show that R (C 4 , ... , C 4 , K 1 , n) = R (C 4 , ... , C 4 , W n) for sufficiently large n. [ABSTRACT FROM AUTHOR]

Abstract For given graphs H 1 ,... , H k , k ≥ 2 , the k -color Ramsey number R (H 1 ,... , H k) is the smallest integer N such that every k -coloring of the edges of a complete graph K N contains a monochromatic copy of H i colored in i , for some i with 1 ≤ i ≤ k. Let C ℓ , K 1 , m and P n denote a cycle of length ℓ , a star of order m + 1 and a path of order n , respectively. In this paper, it is shown that R (C 4 , K 1 , m , P n) ≤ m + n − 1 + ⌈ m + n − 2 ⌉ for all m , n ≥ 2 and R (C 4 , K 1 , m , P n) ≤ m + n − 2 + ⌈ m + n − 2 ⌉ if m + n = ℓ 2 + 3 and ℓ ≥ 1. Moreover, by discussing the local structure of the polarity graph whose vertices are points in the projective plane over Galois fields, we show that the two upper bounds can be attained for some special m and n. These results also extend some known results on R (C 4 , K 1 , m) obtained by Parsons in 1975 and by Zhang et al. recently. [ABSTRACT FROM AUTHOR]