GENERALIZED SPLIT GRAPHS AND RAMSEY NUMBERS

A graph G is called a (p, q)-split graph if its vertex set can be part itioned into A, B so that the order of the largest independent set in A is at most p and the order of the largest complete subgraph in B is at most q. Applying a well-known theorem of Erdos and Rado for Delta-s ystems, it is shown that for fixed p, q, (p, q)-split graphs can be ch aracterized by excluding a finite set of forbidden subgraphs, called ( p, c)-split critical graphs. The order of the largest (p, q)-split cri tical graph, f(p, q), relates to classical Ramsey numbers R(s, t) thro ugh the inequalities 2F(F(R(p + 2, q + 2))) + 1 greater than or equal to f(p, q) greater than or equal to R(p + 2, q + 2) - 1 where F(t) is the smallest number of t-element sets ensuring a t + 1-element Delta-s ystem. Apart from f(1, 1) = 5, all values of f(p, q) are unknown. (C) 1998 Academic Press.