zbMATH — the first resource for mathematics

On $$(1,1)$$-coloring of incidentors of multigraphs of degree 4. (Russian) Zbl 1078.05033
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.

MSC:
 05C15 Coloring of graphs and hypergraphs