On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs (Q1100214)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs |
scientific article |
Statements
On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs (English)
0 references
1988
0 references
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)].
0 references
1-chromatic number
0 references
density
0 references
s-chromatic number
0 references