|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2008, Volume 5, Pages 211–214
(Mi semr101)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Research papers
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
Abstract:
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.
Keywords:
planar graph, 4-choosability, vertex-arboricity.
Received April 25, 2008, published May 5, 2008
Citation:
O. V. Borodin, A. O. Ivanova, “List 2-arboricity of planar graphs with no triangles at distance less than two”, Sib. Èlektron. Mat. Izv., 5 (2008), 211–214
Linking options:
https://www.mathnet.ru/eng/semr101 https://www.mathnet.ru/eng/semr/v5/p211
|
Statistics & downloads: |
Abstract page: | 302 | Full-text PDF : | 69 | References: | 69 |
|