RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2008 Volume 5, Pages 211–214 (Mi semr101)

This article is cited 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.

UDC: 519.172.2

MSC: 05С15

Received April 25, 2008, published May 5, 2008

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024