## Vertex-partitions of planar graphs

Let us consider the following classes of graphs:

• I the class of empty graphs,
• F the class of forests,
• Fk the class of forests with maximum degree at most k,
• P the class of paths,
• Pk the class of paths ol length at most k,
• S the class of star forests,
• Sk the class of star forests with maximum degree at most k,
• Dk the class of graphs with maximum degree at most k,
• dk the class of k-degenerate graphs,
• Ok the class of graphs of order k.

Observe that: d1=F, D0=I, D1=S1=F1

Consider i classes of graphs G1, . . . , Gi. A (G1, . . . , Gi)-partition of a graph G is a vertex-partition into i sets V1,...,Vi such that, for all 1 <= j <= i, the graph G[Vj] induced by Vj belongs to Gj. For example, a (I,F,d2)-partition is a vertex-partition into three sets V1,V2,V3 such that G[V1] is an empty graph, G[V2] is a forest, and G[V3] is a 2-degenerate graph.

### Results

 Girth Vertex-partitions References 3 (I,I,I,I) K. Appel K, W. Haken. Every Planar Map is Four Colorable Part I. Discharging, Illinois Journal of Mathematics 21: 429û490, 1977. K. Appel, W. Haken W, J. Koch. Every Planar Map is Four Colorable Part II. Reducibility, Illinois Journal of Mathematics 21: 491û567, 1977. (I,F,F) O.V. Borodin. A proof of GrünbaumÆs conjecture on the acyclic 5-colorability of planar graphs (russian). Dokl. Akad. Nauk SSSR, 231(1):18û20, 1976. (F2,F2,F2) K.S. Poh. On the linear vertex-arboricity of a plane graph. Journal of Graph Theory, 14(1):73û75, 1990. (F,d2) C. Thomassen. Decomposing a planar graph into degenerate graphs. Journal of Combinatorial Theory, Series B, 65(2):305û314, 1995. (I,d3) C. Thomassen. Decomposing a planar graph into an independent set and a 3-degenerate graph. Journal of Combinatorial Theory, Series B, 83(2):262û271, 2001. 4 (I,I,I) H. Gr÷tzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz f³r dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109û120, 1959. (F,F) Folklore (F,F5) Franþois Dross, Mickael Montassier, Alexandre Pinlou. Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. http://arxiv.org/pdf/1601.01523v1.pdf (I,d2) Folklore 5 (I,F) O.V. Borodin, A.N. Glebov. On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph (russian). Diskretnyi Analiz i Issledovanie Operatsii, 8(4):34û53, 2001. (D1,D10) H. Choi, I. Choi, J. Jeong, G. Suh. (1,k)-coloring of graphs with girth at least 5 on a surface. http://arxiv.org/pdf/1412.0344v1.pdf (D2,D6) O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014. (D3,D5) I. Choi and A. Raspaud. Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Mathematics, 318(4):661û667, 2015. (D4,D4) F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. 6 (D1,D4) O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014. (I,Dk) for any k O.V. Borodin, A.O. Ivanova, M. Montassier, P. Ochem, and A. Raspaud. Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k. Journal of Graph Theory, 65(2):83-93, 2010. (D2,D2) F. Havet, J.-S. Sereni. Improper choosability of graphs and maximum average degree. Journal of Graph Theory, 52(3):181-199, 2006. (P14,P14) M. Axenovich, T. Ueckerdt, and P. Weiner. Splitting planar graphs of girth 6 into two linear forests with short paths. http://arxiv.org/pdf/1507.02815.pdf (O12,O12) L. Esperet and P. Ochem. Islands in graphs on surfaces. http://arxiv.org/pdf/1402.2475v3.pdf 7 (I,D4) O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014. (I,F5) F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf (D1,D1) O.V. Borodin, A. Kostochka, M. Yancey. On 1-improper 2-coloring of sparse graphs. Discrete Mathematics, 313(22):2638-2649, 2013. (I,D2) M. Montassier and P. Ochem. Near-colorings: non-colorable graphs and NP-completness. Electronic Journal of Combinatorics,Volume 22, Issue 1, 2015. 8 (I,D2) O.V. Borodin, A.V. Kostochka. Defective 2-colorings of sparse graphs. Journal of Combinatorial Theory, Series B, 104:72-80, 2014. (I,F3) F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf 9 (I,D1) L. Esperet, M. Montassier, P. Ochem, and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory, 73(1):85-102, 2013. 10 (I,D1) ? Open question. (I,F2) F. Dross, M. Montassier, A. Pinlou. Partitioning sparse graphs into an independent set and a forest of bounded degree. http://arxiv.org/pdf/1606.04394v1.pdf 11 (I,D1) J. Kim, A. Kostochka, X. Zhu.Improper coloring of sparse graphs with a given girth, I: (0,1)-colorings of triangle-free graphs. European Journal of Combinatorics, 42:26-48, 2014.

### Acknowledgements

Thanks to Ilkyoo Choi, Franþois, Dross, Pascal Ochem.

Keywords: graph theory, graphs, partition, vertex, planar graphs, given girth