Graphs with small generalized chromatic number

Abstract

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* of graphs of order n and diameter D ≥ 3 such that, over all graphs G ∈ G*, γ_D-1(G) ∈ Θ(√Dn). Constructions are specified for graphs in the class G*.