The strong chromatic number of a graph

It is shown that there is an absolute constant c with the following property: For any two graphs G 1 = ( V, E 1 ) and G 2 = ( V, E 2 ) on the same set of vertices, where G 1 has maximum degree at most d and G 2 is a vertex disjoint union of cliques of size cd each, the chromatic number of the graph G = ( V, E 1 U E 2 ) is precisely cd . The proof is based on probabilistic arguments.