|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2004, Volume 1, Pages 129–141
(Mi semr12)
|
|
|
|
This article is cited in 34 scientific papers (total 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$.
Received December 1, 2004, published December 14, 2004
Citation:
O. V. Borodin, A. N. Glebov, A. O. Ivanova, T. K. Neustroeva, V. A. Tashkinov, “Sufficient conditions for planar graphs to be $2$-distance $(\Delta+1)$-colorable”, Sib. Èlektron. Mat. Izv., 1 (2004), 129–141
Linking options:
https://www.mathnet.ru/eng/semr12 https://www.mathnet.ru/eng/semr/v1/p129
|
Statistics & downloads: |
Abstract page: | 413 | Full-text PDF : | 86 | References: | 51 |
|