Reading: The size, multipartite Ramsey numbers for C3 versus all graphs up to 4 vertices

A- A+
dyslexia friendly

The size, multipartite Ramsey numbers for C3 versus all graphs up to 4 vertices

Chula Jayawardene,

LK

Department of Mathematics, Faculty of Science, University of Colombo, Colombo 03.

Lilanthi Samarasekara

LK

Department of Mathematics, Faculty of Science, University of Colombo, Colombo 03.

Abstract

In this paper we restrict our attention to finite graphs containing no loops or multiple edges. The multipartite graph Kj×s ( j ≥ 3) consisting of j partite sets of uniform size s is defined as V (Kj×s) = {vmn | m  {1,2,...,j} and n {1,2,...,s} } and E (Kj×s) = {vmn vkl | m,k  {1,2,...,j} and n, l  {1,2,...,s} where k m}. The set of vertices of the mth partite set is denoted by {vmn | 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 Ks → (H,G) and along the same line of reasoning, the multipartite Ramsey number mj (H,G) is defined as the smallest positive integer s such that Kj×s → (H,G). Thus, multipartite Ramsey number mj (C3,G) is defined as the smallest positive integer s such that any red-blue colouring of Kj×s contains a red C3 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 mj (C3,G) when G is any graph up to 4 vertices.
DOI: http://doi.org/10.4038/jnsfsr.v45i1.8039
How to Cite: Jayawardene, C. & 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
0
Views
0