Geodesic
Partition of a~planar graph with girth~7 into two star forests
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 3, pp. 20-46.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2009_16_3_a1,
     author = {D. Zh. Zambalayeva},
     title = {Partition of a~planar graph with girth~7 into two star forests},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {20--46},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_3_a1/}
}
TY  - JOUR
AU  - D. Zh. Zambalayeva
TI  - Partition of a~planar graph with girth~7 into two star forests
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 20
EP  - 46
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_3_a1/
LA  - ru
ID  - DA_2009_16_3_a1
ER  - 
%0 Journal Article
%A D. Zh. Zambalayeva
%T Partition of a~planar graph with girth~7 into two star forests
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 20-46
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_3_a1/
%G ru
%F DA_2009_16_3_a1
D. Zh. Zambalayeva. Partition of a~planar graph with girth~7 into two star forests. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 3, pp. 20-46. http://geodesic.mathdoc.fr/item/DA_2009_16_3_a1/

[1] Borodin O. V., Glebov A. N., “O razbienii ploskogo grafa obkhvata 5 na pustoi i atsiklicheskii podgrafy”, Diskret. analiz i issled. operatsii. Ser. 1, 8:4 (2001), 34–53 | MR | Zbl

[2] Borodin O. V., Ivanova A. O., “Razbienie razrezhennykh ploskikh grafov na dva podgrafa maloi stepeni”, Sib. elektron. mat. izvestiya, 6 (2009), 13–16 ; http://semr.math.nsc.ru/ | MR

[3] Glebov A. N., Zambalaeva D. Zh., “Putevye razbieniya planarnykh grafov”, Sib. elektron. mat. izvestiya, 4 (2007), 450–459 ; http://semr.math.nsc.ru/ | MR | Zbl

[4] Zambalaeva D. Zh., Putevye razbieniya planarnykh grafov, Diplomnaya rabota, NGU, Novosibirsk, 2007, 28 pp.

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

[6] Borodin O. V., “On acyclic colorings of planar graphs”, Discrete Math., 25:3 (1979), 211–236 | DOI | MR | Zbl

[7] Borodin O. V., Kostochka A. V., Sheikh N. N., Yu G., “Decomposing a planar graph with girth 9 into a forest and matching”, Europ. J. Combin., 29:5 (2008), 1235–1241 | DOI | MR | Zbl

[8] 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

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

[10] 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

[11] Chartrand G., Kronk H. V., “The point-arboricity of planar graphs”, J. London Math. Soc., 44:4 (1969), 612–616 | DOI | MR | Zbl

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

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

[14] Fijavz̆ G., Juvan M., Mohar B., S̆krekovski R., “Planar graphs without cycles of specific lengths”, Europ. J. Combin., 23:4 (2002), 377–388 | DOI | MR | Zbl

[15] Grötzsch H., “Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel”, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Natur. Reihe, 8 (1959), 109–120 | MR

[16] Grünbaum B., “Acyclic colorings of planar graphs”, Israel J. Math., 14:3 (1973), 390–408 | DOI | MR | Zbl

[17] Hakimi S. L., Mitchem J., Schmeichel E. F., “Star arboricity of graphs”, Discrete Math., 149:1–3 (1996), 93–98 | DOI | MR | Zbl

[18] Jensen T. R., Toft B., Graph coloring problems, John Wiley Sons Inc., New York, 1995, 295 pp. | MR | Zbl

[19] Kostochka A. V., Melnikov L. S., “Note to the paper of Grünbaum on acyclic colorings”, Discrete Math., 14:4 (1976), 403–406 | DOI | MR | Zbl

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

[21] Nash-Williams C. St. J. A., “Decomposition of finite graphs into forests”, J. London Math. Soc., 39 (1964), 12 | DOI | MR | Zbl

[22] Raspaud Wang W., “On the vertex-arboricity of planar graphs”, Europ. J. Combin., 29:4 (2008), 1064–1075 | DOI | MR | Zbl

[23] Stein S. K., “B-sets and coloring problems”, Bull. Amer. Math. Soc., 76:4 (1970), 805–806 | DOI | MR | Zbl

[24] Stein S. K., “B-sets and planar maps”, Pacific J. Math., 37:1 (1971), 217–224 | MR | Zbl

[25] Wang W., Lih K.-W., “Choosability and edge choosability of planar graphs without 5-cycles”, Appl. Math. Lett., 15:5 (2002), 561–565 | DOI | MR | Zbl

[26] Wegner G., “Note on a paper of B. Grünbaum on acyclic colorings”, Israel J. Math., 14:4 (1973), 409–412 | DOI | MR | Zbl