Search

Abstract For k given graphs G 1 , G 2 , ... , G k , k ≥ 2 , the k -color Ramsey number, denoted by R (G 1 , G 2 , ... , G 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 G i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m and K 1 , n a star of order n + 1. In this paper, firstly we give a general upper bound of R (C 4 , C 4 , ... , C 4 , K 1 , n). In particular, for the 3-color case, we have R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 3 and this bound is tight in some sense. Furthermore, we prove that R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 2 for all n = ℓ 2 − ℓ and ℓ ≥ 2 , and if ℓ is a prime power, then the equality holds. [ABSTRACT FROM AUTHOR]

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 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) shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 and if n is the square of a prime power, then the equality holds. In this paper, by discussing the properties of polarity graphs whose vertices are points in the projective planes over Galois fields, we prove that R ( C 4 , K 1 , q 2 − t ) = q 2 + q − ( t − 1 ) if q is an odd prime power, 1 ≤ t ≤ 2 ⌈ q 4 ⌉ and t ≠ 2 ⌈ q 4 ⌉ − 1 , which extends a result on R ( C 4 , K 1 , q 2 − t ) obtained by Parsons (1976). [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]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest positive integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Sn denote a star of order n and Wm a wheel of order m+1. This paper shows that R(Sn,W6)=2n+1 for n≥3 and R(Sn,Wm)=3n-2 for m odd and n≥m-1≥2. [Copyright &y& Elsevier]

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]

For bipartite graphs H 1 , ... , H μ , μ ≥ 2 , the μ -color bipartite Ramsey number, denoted by R b (H 1 , ... , H μ) , is the least positive integer N such that if we arbitrarily color the edges of a complete bipartite graph K N , N with μ colors, then it contains a monochromatic copy of H i in color i for some i , 1 ≤ i ≤ μ. Let C 4 and K 1 , n be a quadrilateral and a star on n + 1 vertices, respectively. In this paper, we show that the (μ + 1) -color bipartite Ramsey number R b (C 4 , ... , C 4 , K 1 , n) ≤ n + ⌈ 1 2 μ 2 (4 n + μ 2 + 2 μ − 7) + 4 ⌉ + μ 2 + μ 2 − 1. Moreover, using algebraic methods, we construct Ramsey graphs or near Ramsey graphs and determine infinitely many values of R b (C 4 , ... , C 4 , K 1 , n) , which reach the upper bound if μ = 1 , 2 and are at most ⌊ μ 2 ⌋ less than the upper bound if μ ≥ 3. [ABSTRACT FROM AUTHOR]

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 G of order N , either G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n be a tree of order n , S n a star of order n , and F m a fan of order 2 m + 1 , i.e., m triangles sharing exactly one vertex. In this paper, we prove that R ( T n , F m ) = 2 n − 1 for n ≥ 3 m 2 − 2 m − 1 , and if T n = S n , then the range can be replaced by n ≥ max { m ( m − 1 ) + 1 , 6 ( m − 1 ) } , which is tight in some sense. [ABSTRACT FROM AUTHOR]