# zbMATH — the first resource for mathematics

On the $$(p,q)$$-coloring of incidentors of an undirected multigraph. (Russian) Zbl 1249.05143
Summary: Let $$0\leq p\leq q$$. A proper coloring of the set of incidentors of an undirected multigraph is called a $$(p,q)$$-coloring if for every edge of $$G$$ the module of the difference between the colors of its incidentors lies in the interval $$[p,q]$$. The minimum number of colors in any $$(p,q)$$-coloring of all incidentors of the multigraph $$G$$ is called the $$(p,q)$$-chromatic number of $$G$$ and is denoted by $$\chi (p,q,G)$$. For $$G$$ being a homogeneous multigraph of degree $$\Delta$$, we find the exact values of $$\chi (p,q,G)$$ for all $$q\geq p\geq 1$$. These exact values depend only on $$\Delta$$ and do not depend on other structural features of multigraphs $$G$$. For non-homogeneous multigraph, we find estimates of $$(p, q)$$-chromatic numbers.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory