A generalization of Ramsey theory for linear forests

Abstract

Chung and Liu defined the d-chromatic Ramsey numbers as a generalization of Ramsey numbers by replacing the usual condition with a slightly weaker condition. Let 1<d<c and let . Assume A ₁, A ₂, …, A _t are all d-subsets of a set containing c distinct colours. Let G ₁, G ₂, …, G _t be graphs. The d-chromatic Ramsey number denoted by is defined as the least number p such that, if the edges of the complete graph K _p are coloured in any fashion with c colours, then for some i, the subgraph whose edges are coloured by colours in A _i contains a G _i . In this paper, we determine for t=3, 4 and for linear forests G _i , 1≤i≤t, when G ₁ has at most one odd component and G _j , 2≤j≤t−1, either is a path or has no odd component. Consequently, these numbers are determined when G _i , 1≤i≤t, is either a path or a stripe.

Keywords:

• d-chromatic Ramsey number
• edge colouring
• weakened Ramsey numbers

2010 AMS Subject Classifications :

• 05C55
• 05D10