Volume 16, No 4, 2009, P. 21-30

UDC 519.718
V. G. Vizing
Vertex colorings of graph with the majority restrictions on the consuming colors

Abstract:
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.

Keywords: majority prescription, feasible coloring, chromat of graph.

Vizing Vadym Georgievich ¹
1. Odessa National Academy of Food Technologies,
112 Kanatnaya str., 65039 Odessa, Ukraine
e-mail: vizing@paco.net