RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2008, том 5, страницы 211–214 (Mi semr101)

Эта публикация цитируется в 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.

УДК: 519.172.2

MSC: 05С15

Поступила 25 апреля 2008 г., опубликована 5 мая 2008 г.

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024