Nested colorings of graphs.
David Cook · Australas. J Comb. · 2015
We develop a new upper bound, called the nested chromatic number, for the chromatic number of a finite simple graph. This new invariant can be computed in polynomial time, unlike the standard chromatic number which is NP -hard. We further develop multiple distinct bounds on the nested chromatic number using common properties of graphs. We also determine the behavior of the nested chromatic number under several graph operations, including the direct, Cartesian, strong, and lexicographic product. Moreover, we classify precisely the possible nested chromatic numbers of finite simple graphs on a fixed number of vertices with a fixed chromatic number.