# zbMATH — the first resource for mathematics

Sufficient conditions for the minimum 2-distance colorability of plane graphs of girth 6. (Russian. English summary) Zbl 1119.05039
Summary: A trivial lower bound for the 2-distance chromatic number $$\chi_2(G)$$ of any graph $$G$$ with maximum degree $$\Delta$$ is $$\Delta+1$$. It is known that if $$G$$ is planar and its girth is at least 7, then for large enough $$\Delta$$ this bound is sharp, while for girth 6 it is not. We prove that if $$G$$ is planar, its girth is 6, every edge is incident with a 2-vertex, and $$\Delta\geq 31$$, then $$\chi_2(G)=\Delta+1$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
graph coloring problem
Full Text: