On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs
For graph G let \(d_ s\) be the maximum size of any subset U of V(G) such that any two vertices of U have distance at most s. Let \(\gamma_ s(G)\), the s-chromatic number of G, be the minimum number of colors which can be used on V(G) such that any two vertices at distance at most s have different colors. Also let \(v_ s(h)\) denote the maximum integer n such that all graphs of order less than n have \(\gamma_ s-d_ s<h\). Theorem: \(v_ 2(h)\leq 6h\) for all \(h\geq 3\). This improves the bound of 8h given by \textit{M. Gionfriddo} [Riv. Mat. Univ. Parma, IV. Ser. 8, 1-7 (1982; Zbl 0519.05031)].
scientific article; zbMATH DE number 4041943
scientific article