Interval vertex coloring

In this paper we consider various vertex versions of interval edge colorings. We distinguish two types of interval vertex colorings - an open and a closed interval vertex coloring, which are defined in such a way that colors used on open or closed neighborhood of each vertex form an integer interval, respectively. These colorings need not to be necessarily proper, and as coloring of all vertices with only one color is both open and closed, a natural goal is to maximize the total number of colors used for these colorings. We discuss some properties of the corresponding chromatic numbers and conditions for the existence of a proper (open and closed) interval vertex colorings. In the case of open interval coloring we show that only bipartite graphs admit a proper open interval vertex coloring. We also describe a technique for obtaining a closed interval vertex coloring of a tree with the maximum possible number of colors, where the resulting coloring is in fact proper. Finally, we propose some open problems concerning interval vertex colorings in general.