On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs
type: Item
instance of: scholarly article
title: On the parameter \(v_ 2(h)\) for \(L_ 2\)-coloured graphs
zbMATH Open document ID: 0639.05021
DOI: 10.1016/0012-365X(88)90046-5
author: Salvatore Milici
author: Mario Gionfriddo
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4041943
zbMATH Keywords: 1-chromatic number
zbMATH Keywords: density
zbMATH Keywords: s-chromatic number
reviewed by: John Mitchem
MaRDI profile type: Publication
cites work: Q4152561
cites work: Q4198788
cites work: Q3669442
cites work: Parallel concepts in graph theory
cites work: Q5552096
cites work: Brève communication. Sur le nombre chromatique $K(p, G)$ des graphes
cites work: Q4101847
Recommended article: On some \(L(2, 1)\)-coloring parameters of certain graph classes
Recommended article: On L2-Golourings of a Graph
Recommended article: On the parameterm2(h) for graphs
Recommended article: On N2-vertex coloring of graphs
Recommended article: Q3429489
Recommended article: Holes in \(L(2,1)\)-coloring on certain classes of graphs
Recommended article: On 2-Colorings of Hypergraphs
Recommended article: Q3171038
Recommended article: Q4391697
Recommended article: Q4668721
description: scientific article; zbMATH DE number 4041943