Vertex colorings of graph with the majority restrictions on the consuming colors

Vertex colorings of a graph under the condition that every vertex has the maximal feasible color are considered. The chromatical criterion for such prescription which generalizes the Vitaver theorem is given. We estimate the maximal value of the prescribed color needed for a prescription to be chromatical. The analogies of the Nordhause–Gaddum theorem on interdependence of chromatic characteristics of the graph and the complementary graph are obtained. Bibl. 7.