|
Сибирские электронные математические известия, 2008, том 5, страницы 211–214
(Mi semr101)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Статьи
List $2$-arboricity of planar graphs with no triangles at distance less than two
O. V. Borodina, A. O. Ivanovab a Institute of Mathematics, Novosibirsk, Russia
b Yakutsk State University, Yakutsk, Russia
Аннотация:
It is known that not all planar graphs are $4$-choosable; neither all of them are vertex $2$-arborable. However,
planar graphs with no triangles at distance less than two are known to be $4$-choosable (Lam, Shiu, Liu, 2001) and $2$-arborable (Raspaud, Wang, 2008).
We give a common extension of these two last results in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph with no triangles at distance less than two is list $2$-arborable.
Ключевые слова:
planar graph, $4$-choosability, vertex-arboricity.
Поступила 25 апреля 2008 г., опубликована 5 мая 2008 г.
Образец цитирования:
O. V. Borodin, A. O. Ivanova, “List $2$-arboricity of planar graphs with no triangles at distance less than two”, Сиб. электрон. матем. изв., 5 (2008), 211–214
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr101 https://www.mathnet.ru/rus/semr/v5/p211
|
Статистика просмотров: |
Страница аннотации: | 289 | PDF полного текста: | 67 | Список литературы: | 65 |
|