Sufficient conditions for planar graphs to be 2-distance (\(\Delta+1\))-colourable. (Russian. English summary) Zbl 1076.05032

Borodin, O. V.; Glebov, A. N.; Ivanova, A. O.; Neustroeva, T. K.; Tashkinov, V. A.

Sib. Èlektron. Mat. Izv. 1, 129-141 (2004).

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