|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2007, Volume 4, Pages 450–459
(Mi semr167)
|
|
|
|
This article is cited in 17 scientific papers (total 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.
Received October 30, 2007, published November 8, 2007
Citation:
A. N. Glebov, D. Zh. Zambalayeva, “Path partitions of planar graphs”, Sib. Èlektron. Mat. Izv., 4 (2007), 450–459
Linking options:
https://www.mathnet.ru/eng/semr167 https://www.mathnet.ru/eng/semr/v4/p450
|
Statistics & downloads: |
Abstract page: | 410 | Full-text PDF : | 91 | References: | 60 |
|