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

Sib. Èlektron. Mat. Izv., 2007 Volume 4, Pages 450–459 (Mi semr167)

This article is cited in 17 papers

Research papers

Path partitions of planar graphs

A. N. Glebova, D. Zh. Zambalayevab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Novosibirsk State University

Abstract: A graph $G$ is said to be $(a,b)$-partitionable for positive intergers $a,b$ if its vertices can be partitioned into subsets $V_1,V_2$ such that in $G[V_1]$ any path contains at most $a$ vertices and in $G[V_2]$ any path contains at most $b$ vertices. Graph $G$ is $\tau$-partitionable if it is $(a,b)$-partitionable for any $a,b$ such that $a+b$ is the number of vertices in the longest path of $G$. We prove that every planar graph of girth $5$ is $\tau$-partitionable and that planar graphs with girth $8$, $9$ and $16$ are $(2,3)$-, $(2,2)$- and $(1,2)$-partitionable respectively.

UDC: 519.172.2

MSC: 05C15

Received October 30, 2007, published November 8, 2007



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024