Coloring the vertices of a graph with majority restrictions on colors
V. G. Vizing · Journal of Applied and Industrial Mathematics · 2010
The problem of coloring the vertices of a graph is under consideration assuming that the majority (maximal admissible) color is specified for each vertex. A criterion given for the chromaticity of this prescription generalizes the Vitaver theorem. An estimate of the greatest value of a majority color can be required for the chromaticity of the prescription. Some analogs of the Nordhaus-Gaddum theorem are proved concerning the relations among the chromatic characteristics of a graph and its complement.