×

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
PDF BibTeX XML Cite
Full Text: EMIS EuDML