Graphs with small generalized chromatic number

Let G = (V, E) denote a finite simple undirected connected graph of order n = \V\ and diameter D. For any integer k is an element of [1, D], a proper k-colouring of G is a labelling of the vertices V such that no two distinct vertices at distance k or less have the same label. We let gamma(k) (G), the k-chromatic number of G, denote the least number of labels required to achieve a proper k-colouring of G. In this paper we show that there exists an infinite class G* of graphs of order n and diameter D greater than or equal to 3 such that, over all graphs G is an element of G*, gamma(D-1)(G) is an element of Theta(root DN). Constructions are specified for graphs in the class G*.