Volume 16, No 3, 2009, P. 20-46

UDC 519.172.2
D. Zh. Zambalayeva
Partition of a planar graph with girth 7 into two star forests

Abstract:
We prove that the vertex set of any planar graph with girth at least 7 can be partitioned into two subsets such that each subset induces a star forest, i. e. a collection of vertex disjoint paths.
Bibl. 26.

Keywords: planar graph, girth, path partition.

Zambalayeva Dolgor Zhamyanovna ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: dolgor@ngs.ru