|
Сибирские электронные математические известия, 2004, том 1, страницы 129–141
(Mi semr12)
|
|
|
|
Эта публикация цитируется в 34 научных статьях (всего в 34 статьях)
Статьи
Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов
О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов
Аннотация:
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$.
Поступила 1 декабря 2004 г., опубликована 14 декабря 2004 г.
Образец цитирования:
О. В. Бородин, А. Н. Глебов, А. О. Иванова, Т. К. Неустроева, В. А. Ташкинов, “Достаточные условия $2$-дистанционной $\Delta+1$ раскрашиваемости плоских графов”, Сиб. электрон. матем. изв., 1 (2004), 129–141
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr12 https://www.mathnet.ru/rus/semr/v1/p129
|
Статистика просмотров: |
Страница аннотации: | 424 | PDF полного текста: | 92 | Список литературы: | 56 |
|