Volume 20, No 1, 2013, P. 3-11

UDC 519.718
Vizing V. G. 
Half-chromatic number of graph

The notion of a half-chromatic number is introduced for graphs with a nonempty set of edges. It is proved that the difference between the half-chromatic number and a half of the chromatic number is at most 1.
Bibliogr. 5.

Keywords: chromatic number, half-chromatic number, injective coloring.

Vizing Vadym Georgievich 1
1. 18/2 Varnenskaya St., Apt. 26, 65070 Odessa, Ukraine
e-mail: vizing@paco.net

 © Sobolev Institute of Mathematics, 2015