Mathematika

Research Article

On circuits and subgraphs of chromatic graphs

P. Erdösa1

a1 University College, London, W.C.I.

A graph is said to be k-chromatic if its vertices can be split into k classes so that two vertices of the same class are not connected (by an edge) and such a splitting is not possible for k−1 classes. Tutte was the first to show that for every k there is a k-chromatic graph which contains no triangle [1].

(Received November 13 1962)