Chromatic neighborhood sets

For each vertex v in a graph G, we denote by chi(v) the chromatic number of the subgraph induced by its neighborhood, and we set chi(N)(G) -= {chi(v): v is an element of V(G)}. We characterize those sets X for which there exi sts some G of prescribed size with X = chi(N)(G), and prove a related conje cture of Fajtlowicz. We also discuss those graphs that are extremal with re spect to chi(N)(G). (C) 1999 John Wiley & Sons, Inc.