Search

Let G 1 , G 2 , ... , G c be arbitrary graphs. By G → (G 1 , G 2 , ... , G c) , we mean if the edges of G are partitioned into c disjoint color classes giving c graphs H 1 , H 2 , ... , H c , then at least one H i has a subgraph isomorphic to G i. The Ramsey number R (G 1 , G 2 , ... , G c) is the smallest positive integer n such that K n → (G 1 , G 2 , ... , G c). In this paper, we extend the result of Cockayne and Lorimer on the Ramsey number of stripes allowing host graphs with the corresponding Ore-type condition: If t ≥ 1 and n 1 , n 2 , ... , n c , n 1 = max ⁡ { n 1 , n 2 , ... , n c } , are positive integers and G is a graph with at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 vertices such that for each pair of non-adjacent vertices, the sum of the number of their non-neighbors is at most 2 max ⁡ { t , n 1 } − 1 , then G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Consequently, we prove that if G is a graph with chromatic number at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 , then G → (S t , n 1 K 2 , n 2 K 2 , ... , n c K 2) , where S t is the star graph with t edges. In addition, for given graph G , the Ramsey closure of G , denoted by C (G) , is defined and we prove that if G is a graph with at least max ⁡ { t , n 1 } + ∑ i = 1 c (n i − 1) + 1 vertices, then G → (n 1 K 2 , n 2 K 2 , ... , n c K 2) if and only if C (G) → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Thus, a condition that forces C (G) → (n 1 K 2 , n 2 K 2 , ... , n c K 2) also forces G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). As a result, a condition is provided on the degree sequence of a graph G such that under this condition G → (n 1 K 2 , n 2 K 2 , ... , n c K 2). Further, this article provides a sharp bound for the maximum number of edges in a simple graph G such that G ↛ (n 1 K 2 , n 2 K 2 , ... , n c K 2). We also establish the uniqueness of such extremal graphs. This result provides a far-reaching generalization of an important classical result of Erdős and Gallai and also giving a new proof for the graph case of the conjecture of Erdős dating back to 1965, known as the Erdős' matching conjecture. [ABSTRACT FROM AUTHOR]