Path partitions of planar graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 450-459
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{SEMR_2007_4_a25,
author = {A. N. Glebov and D. Zh. Zambalayeva},
title = {Path partitions of planar graphs},
journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
pages = {450--459},
publisher = {mathdoc},
volume = {4},
year = {2007},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/SEMR_2007_4_a25/}
}
A. N. Glebov; D. Zh. Zambalayeva. Path partitions of planar graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 450-459. http://geodesic.mathdoc.fr/item/SEMR_2007_4_a25/