ON A CONJECTURE OF RODL AND VOIGT

We prove that if lambda is an infinite cardinal number and G is any gr aph of cardinality kappa = lambda+ which is a union of a finite number of forests, then there is a graph H(k) of size kappa (which does not depend upon G) so that H(kappa) --> (G)lambda1. Rodl and Voight conjec tured that there is such a graph H(kappa) for the special case when G is the regular tree on kappa in which every vertex has degree kappa. W e also prove that if a graph is the union of n forests, then it has co louring number 2n. (C) 1994 Academic Press, inc.