The chromatic neighborhood sequence of a graph is the list of the chromatic numbers of the subgraphs induced by the neighborhoods of the vertices. There are simple necessary and sufficient conditions for a sequence of numbers to be the degree sequence of a graph. For chromatic neighborhood sequences the situation seems more complicated, and we will give some first results. We study the maximum multiplicity of this sequence, proving, amongst other things, that if a chromatic neighborhood sequence has $ t$ distinct values, the largest value being $d_t$, then there is a value with multiplicity at least ${2d_t\over t}(1-\Theta(\ln t/t))$. This bound is asymptotically tight.

CONE April 2000.