|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2006, Volume 3, Pages 441–450
(Mi semr219)
|
|
|
|
This article is cited in 13 scientific papers (total in 13 papers)
Research papers
Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth $6$
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
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$. It is known that if $G$ is planar and its girth is at least $7$, then for large enough $\Delta$ this bound is sharp, while for girth $6$ it is not true. We prove that if $G$ is planar, its girth is $6$, every edge is incident with a $2$-vertex, and $\Delta\ge31$, then $\chi_2(G)=\Delta+1$.
Received December 1, 2006, published December 29, 2006
Citation:
O. V. Borodin, A. O. Ivanova, T. K. Neustroeva, “Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth $6$”, Sib. Èlektron. Mat. Izv., 3 (2006), 441–450
Linking options:
https://www.mathnet.ru/eng/semr219 https://www.mathnet.ru/eng/semr/v3/p441
|
Statistics & downloads: |
Abstract page: | 462 | Full-text PDF : | 64 | References: | 50 |
|