Construction of Special Edge-Chromatic Graphs

Abstract

The configuration formed by N points in general position in space, together with the lines joining them in pairs will be called an N-clique. The N-clique is coloured by assigning to each edge exactly one colour from a set of t possible colours. A theorem due to Ramsey [4] ensures the existence of a least integer M(q 1 , q 2 , …, q t ) such that if N ≥ M, any such colouring of the N-clique must contain either a q 1 -clique entirely of colour 1, or a q 2 -clique of colour 2, …, or a q t -clique of colour t. Another proof of Ramsey's theorem is given by Ryser [5].