Multicoloring the incidentors of a weighted undirected multigraph

摘要

Under consideration are the undirected multigraphs with weighted edges. In multicoloring incidentors, to each incidentor there is assigned a multicolor; i. e., an interval of colors whose length is equal to the weight of the incidentor. A multicoloring is proper if the multicolors of every two adjacent or mated incidentors are disjoint. We give some lower and upper estimates for the minimal number of colors necessary for a proper multicoloring of all incidentors of a graph.