On \((1,1)\)-coloring of incidentors of multigraphs of degree 4. (Russian) Zbl 1078.05033

Pyatkin, A. V.

Diskretn. Anal. Issled. Oper., Ser. 1 11, No. 3, 59-62 (2004).

Let \(G=(V,E)\) be an oriented multigraph without loops, where \(V\) is the set of vertices and \(E\) is the set of edges. An ordered pair \((v,e)\) is said to be an incidentor if the edge \(e \in E\) is incident to the vertex \(v \in V\). Thus, every edge \(e=uv\) is associated with the initial incidentor \((u,e)\) and the terminal incidentor \((v,e)\). Let \(I\) be the set of all incidentors of the multigraph \(G\). A coloring \(f\: I \to \mathbb Z_+\) is said to be a \((1,1)\)-coloring if \(f((v,e)) - f((u,e))=1\) for every edge \(e=uv\). Let \(\chi_{1,1}(G)\) be the \((1,1)\)-chromatic number of \(G\), i.e., the minimal number of colors sufficient to produce a \((1,1)\)-coloring of \(G\). The main result of the paper states that for every multigraph \(G\) of degree \(4\) the inequality \(\chi_{1,1} (G) \leq 5\) holds.

Reviewer: A. Yu. Vesnin (Novosibirsk)

MSC:

05C15

Coloring of graphs and hypergraphs