Sharp Bounds and Precise Values for the N_i-Chromatic Number of Graphs

Abstract: Let

G

be a connected undirected graph.~A vertex coloring

f

of

G

is an

N_{i}

-vertex coloring if for each vertex

x

in

G

, the number of different colors assigned to

N_{G} (x)

is at most

i

.~The

N_{i}

-chromatic number of

G

, denoted by

t_{i} (G)

, is the maximum number of colors which are used in an

N_{i}

-vertex coloring of

G

. In this paper, we provide sharp bounds for

t_{i} (G)

of a graph

G

in terms of its vertex cover number, maximum degree and diameter, respectively. We also determine precise values for

t_{i} (G)

in some cases.

This page was built for publication: Sharp Bounds and Precise Values for the $N_i$-Chromatic Number of Graphs