O. V. Borodin, A. O. Ivanova, T. K. Neustroeva, “<nobr>$2$</nobr>-distance coloring of sparse planar graphs”, Sib. Èlektron. Mat. Izv., 2004, Volume 1,Pages <nobr>76

This article is cited in 21 papers

Research papers

$2$-distance coloring of sparse planar graphs

O. V. Borodin^a, A. O. Ivanova^b, T. K. Neustroeva^b

^a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
^b Yakutsk State University, Institute for Mathematics and Informatics

Abstract: Clearly, the 2-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is at least $\Delta+1$. We prove that if $G$ is planar and its girth is large enough (w.r.t. a fixed $\Delta$), then $\chi_2(G)=\Delta+1$.

UDC: 519.172.2

MSC: 05С15

Received October 29, 2004, published November 16, 2004