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.

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