# zbMATH — the first resource for mathematics

2-distance coloring of sparse planar graphs. (Russian. English summary) Zbl 1077.05040
Let $$G = (V(G), E(G))$$ be a graph without loops and multiple edges. Denote by $$d(u,v)$$ the distance between vertices $$u$$ and $$v$$ of $$G$$. A coloring $$f \: V(G) \to \{1, 2, \dots, k\}$$ is said to be a 2-distance coloring if, for every two vertices $$u$$ and $$v$$ such that $$d(u,v)\leq 2$$, the inequality $$f(u) \neq f(v)$$ holds. The minimal number of colors among all 2-distance colorings of $$G$$ is referred to as 2-distance chromatic number of $$G$$ and denoted by $$\chi_2 (G)$$. Obviously, if $$G$$ is of maximal degree $$\Delta = \Delta (G)$$ then $$\chi_2(G) \geq \Delta + 1$$. The authors prove that if $$G$$ is planar and its girth (the length of maximal cycle) is large enough (with respect to a fixed $$\Delta$$) then $$\chi_2 (G) = \Delta +1$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
coloring; maximal cycle
Full Text: