A graph G is called a ( p, q)-split graph if its vertex set can be partitioned 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 Erdo s and Rado for 2-systems, it is shown that for fixed p, q, ( p, q)-split graphs can be characterized by excluding a finite set of forbidden subgraphs, called ( p, q)split critical graphs. The order of the largest ( p, q)-split critical graph, f ( p, q), relates to classical Ramsey numbers R(s, t) through the inequalities
where F(t) is the smallest number of t-element sets ensuring a t+1-element 2-system. Apart from f (1, 1)=5, all values of f ( p, q) are unknown.
1998 Academic Press
Split graphs have been introduced by Fo ldes and Hammer in [FH] as graphs whose vertices can be partitioned into a complete graph and an independent set. It was proved in [FH] that split graphs can be characterized by the exclusion of three induced subgraphs: C 4 , 2K 2 , and C 5 . (The same result is obtained independently in a slightly more general form in [GL] in the context of 2-track interval systems.) A natural generalization of split graphs have been considered in [EG]; here we shall use a special case of that definition. First some more or less standard terminology is summarized.
We consider finite undirected simple graphs G=(V, E), where V, E are the vertex set and edge set of G, respectively. The numbers |V|, |E| are called the order and the size of the graph G. For A V, G[A] denotes the subgraph of G induced by A, if G is clear from the context, [A] will be used. As usual, :(G) denotes the order of the largest independent set of G