Ramsey Numbers and Graph Parameters

Abstract According to Ramsey’s Theorem, for any natural p and q there is a minimum number R (p, q) such that every graph with at least R (p, q) vertices has either a clique of size p or an independent set of size q. In the present paper, we study Ramsey numbers R (p, q) for graphs in special classes. It is known that for graphs of bounded co-chromatic number Ramsey numbers are upper-bounded by a linear function of p and q. However, the exact values of R (p, q) are known only for classes of graphs of co-chromatic number at most 2. In this paper, we determine the exact values of Ramsey numbers for classes of graphs of co-chromatic number at most 3. It is also known that for classes of graphs of unbounded splitness the value of R (p, q) is lower-bounded by (p-1) (q-1) +1 (p - 1) (q - 1) + 1. This lower bound coincides with the upper bound for perfect graphs and for all their subclasses of unbounded splitness. We call a class Ramsey-perfect if there is a constant c such that R (p, q) = (p-1) (q-1) +1 R (p, q) = (p - 1) (q - 1) + 1 for all p, q c p, q ≥ c in this class. In the present paper, we identify a number of Ramsey-perfect classes which are not subclasses of perfect graphs.