RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2004 Volume 1, Pages 129–141 (Mi semr12)

This article is cited in 34 papers

Research papers

Sufficient conditions for planar graphs to be $2$-distance $(\Delta+1)$-colorable

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


Abstract: 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\ge 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$.

UDC: 519.172.2

MSC: 05С15

Received December 1, 2004, published December 14, 2004



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024