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 ∈ [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 γ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* …