|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2004, Volume 1, Pages 76–90
(Mi semr7)
|
|
|
|
This article is cited in 21 scientific papers (total in 21 papers)
Research papers
$2$-distance coloring of sparse planar graphs
O. V. Borodina, A. O. Ivanovab, T. K. Neustroevab 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$.
Received October 29, 2004, published November 16, 2004
Citation:
O. V. Borodin, A. O. Ivanova, T. K. Neustroeva, “$2$-distance coloring of sparse planar graphs”, Sib. Èlektron. Mat. Izv., 1 (2004), 76–90
Linking options:
https://www.mathnet.ru/eng/semr7 https://www.mathnet.ru/eng/semr/v1/p76
|
Statistics & downloads: |
Abstract page: | 449 | Full-text PDF : | 91 | References: | 70 |
|