On N2-vertex coloring of graphs
Saieed Akbari, Nazanin Alipourfard, P. Jandaghi, M. Mirtaheri · Discrete Mathematics Algorithms and Applications · 2017
Let [Formula: see text] be a graph. A vertex coloring [Formula: see text] of [Formula: see text] is called [Formula: see text]-vertex coloring if [Formula: see text] for every vertex [Formula: see text] of [Formula: see text], where [Formula: see text] is the set of colors of vertices adjacent to [Formula: see text]. Let [Formula: see text] be the maximum number of colors used in an [Formula: see text]-vertex coloring of [Formula: see text]. We provide some lower and upper bounds for [Formula: see text] in terms of girth, diameter or size of [Formula: see text]. Also, for every tree [Formula: see text], we obtain [Formula: see text].