Authors:

Abstract

In this paper we restrict our attention to finite graphs containing no loops or multiple edges. The multipartite graph K_j×s ( j ≥ 3) consisting of j partite sets of uniform size s is defined as V (K_j×s) = {v_mn | m  {1,2,...,j} and n {1,2,...,s} } and E (K_j×s) = {v_mn v_kl | m,k  {1,2,...,j} and n, l  {1,2,...,s} where k ≠ m}. The set of vertices of the m^th partite set is denoted by {v_mn | n  {1,2,...,s}}. If for every two-colouring (red and blue) of the edges of a graph K, there exists a copy of H in the first colour (red) or a copy of G in the second colour (blue), we write K → (H,G). Given two simple graphs H and G, the Ramsey number r(H,G) is defined as the smallest positive integer s such that K_s → (H,G) and along the same line of reasoning, the multipartite Ramsey number m_j (H,G) is defined as the smallest positive integer s such that K_j×s → (H,G). Thus, multipartite Ramsey number m_j (C₃,G) is defined as the smallest positive integer s such that any red-blue colouring of K_j×s contains a red C₃ or a blue G. Since only a few multipartite Ramsey numbers for pairs of graphs have been found so far, in this paper we find all such multipartite Ramsey numbers m_j (C₃,G) when G is any graph up to 4 vertices.

Keywords: Combinatorics ,   graph theory ,   mathematics ,   multipartite Ramsey numbers ,   Ramsey theory  

How to Cite: Jayawardene, C. and Samarasekara, L., 2017. The size, multipartite Ramsey numbers for C3 versus all graphs up to 4 vertices. Journal of the National Science Foundation of Sri Lanka, 45(1), pp.67–72. DOI: http://doi.org/10.4038/jnsfsr.v45i1.8039