Geodesic
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/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - D. Zh. Zambalayeva
TI  - Path partitions of planar graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2007
SP  - 450
EP  - 459
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2007_4_a25/
LA  - ru
ID  - SEMR_2007_4_a25
ER  - 
%0 Journal Article
%A A. N. Glebov
%A D. Zh. Zambalayeva
%T Path partitions of planar graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2007
%P 450-459
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2007_4_a25/
%G ru
%F 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/

[1] Melnikov L. S., Petrenko I. V., “O putevykh yadrakh i razbieniyakh v neorientirovannykh grafakh”, Diskretnyi analiz i issledovanie operatsii, 9:1(2) (2002), 21–35 | MR

[2] Borowiecki M., Broere I., Frick M., Mihok P., Semanisin G., “A survey of hereditary properties of graphs”, Discussiones Mathematicae Graph Theory, 17:1 (1997), 5–50 | MR | Zbl

[3] Broere I., Dorfling M., Dunbar J. E., Frick M., “A path (ological) partition problem”, Discussiones Mathematicae Graph Theory, 18:1 (1998), 113–125 | MR | Zbl

[4] Broere I., Hajnal P., Mihok P., Semanisin G., “Partition problems and kernels of graphs”, Discussiones Mathematicae Graph Theory, 17:2 (1997), 311–313 | MR | Zbl

[5] Dunbar J. E., Frick M., “Path kernels and partitions”, Math. Combin. Comput., 31 (1999), 137–149 | MR | Zbl

[6] Dunbar J. E., Frick M., Bullock F., “Path partitions and Pn-free sets”, Discrete Math., 289:1–3 (2004), 145–155 | DOI | MR | Zbl

[7] Mihok J., Graphs, hypergraphs and matroids, Higher College Engrg., Zielon Gora, 1985