Chromatic neighborhood sets

For each vertex v in a graph G, we denote by χ_v the chromatic number of the subgraph induced by its neighborhood, and we set χ_N(G) = {χ_v: v ∈ V(G)}. We characterize those sets X for which there exists some G of prescribed size with X = χ_N(G), and prove a related conjecture of Fajtlowicz. We also discuss those graphs that are extremal with respect to χ_N(G). © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 303–311, 1999