TWO RESULTS ON GENERALIZED CHROMATIC NUMBERS

Abstract

The m'th chromatic number X_m(G) of a graph G is the least number of colours required to colour the vertices of G such that no m-clique of G is mono-coloured. For each k ≥ 2 and m ≥ 2 we determine for which r a graph G with m'th chromatic number k and clique number r exists. We also determine for which n a graph G exists with X_n (G + K) = X_m (G) = k.