zbMATH — the first resource for mathematics

Sufficient conditions for planar graphs to be 2-distance ($$\Delta+1$$)-colourable. (Russian. English summary) Zbl 1076.05032
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$$. We prove that if $$G$$ is planar and its girth is at least 7, then $$\chi_2(G)=\Delta+1$$ whenever $$\Delta\geq 30$$. On the other hand, we construct planar graphs with girth 5 and 6 that have arbitrarily large $$\Delta$$ and $$\chi_2(G) > \Delta+1$$.

MSC:
 05C15 Coloring of graphs and hypergraphs
Keywords:
coloring; diameter; chromatic number
Full Text: