Volume 21, No 4, 2014, P. 33-41

UDC 519.8
V. G. Vizing
On multicoloring of incidentors of a weighted oriented multigraph

Abstract:
Directed multigraphs with weighted arcs are considered. In multicoloring of incidentors, every incidentor should be assigned with a multicolor, i. e. an interval of colors whose length is equal to the weight of the incidentor. A multicoloring is admissible if the multicolors of adjacent incidentors do not intersect and for every arc the left end of its initial incidentor is not bigger than the left end of its final incidentor. Lower and upper bounds for the minimum number of colors necessary for such multicoloring of all incidentors of a multigraph are presented.
Ill. 1, bibliogr. 5.

Keywords: incidentor, multicoloring, incidentor multichromatic number.

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