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\).

05C15 Coloring of graphs and hypergraphs
Full Text: Link EuDML