A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, …, xp-1 of the same class with dist(xi, xi+1) ⩽ f(k) for each i, 0 ⩽ i ⩽ p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class. We prove that f(k) < 12k when the order of the graph is ⩾ k(k − 2) + 1.