On small graphs with highly imperfect powers

AbstractLet an integer s ⩾ 1 and a graph G be given. Let us denote by χs(G) the smallest integer χ for which there exists a vertex-colouring of G with χ colours such that any two distinct vertices of the same colour are at a distance greater than s. Let us denote by ωs(G) the maximal cardinality of a subset of the vertices of G with diameter at most s. Clearly χs(G) ⩾ ωs(G). For s ⩾ 1 and h ⩾ 0 set γs(G) = χs(G)−ωs(G) and νs(h) = max{n ϵ N: for any graphG, |G| < n implies γs(G)<h}. Gionfriddo (1987) has given estimates for νs(h). We improve the recent bound ν2(h) ⩽ 6h (h⩾3) of Gionfriddo and Milici (1988) to ν2(h) ⩽ 5h (h⩾3). More generally, we give the following tight bounds for arbitrary s⩾ 1 and large enough h: 2h + (hlogh)121232⩽νs(h) ⩽ 2h + h1−ϵs, where ϵs> 0 depends only on s. The upper bound is proved entirely by constructive methods