Partitioning planar graph of girth 5 into two forests with maximum degree 4

Chen, Min ; Raspaud, André ; Wang, Weifan ; Yu, Weiqiang

Czechoslovak Mathematical Journal, Tome 74 (2024) no. 2, pp. 355-366

Abstract (VO)

Given a graph $G=(V, E)$, if we can partition the vertex set $V$ into two nonempty subsets $V_1$ and $V_2$ which satisfy $\Delta (G[V_1])\le d_1$ and $\Delta (G[V_2])\le d_2$, then we say $G$ has a $(\Delta _{d_{1}},\Delta _{d_{2}})$-partition. And we say $G$ admits an $(F_{d_{1}}, F_{d_{2}})$-partition if $G[V_1]$ and $G[V_2]$ are both forests whose maximum degree is at most $d_{1}$ and $d_{2}$, respectively. We show that every planar graph with girth at least 5 has an $(F_4, F_4)$-partition.

Détail

DOI : 10.21136/CMJ.2024.0394-21

Classification : 05C10, 05C69
Keywords: vertex partition; girth; forest; maximum degree

Bibliographie

[1] Appel, K., Haken, W.: Every planar map is four colorable. I. Discharging. Ill. J. Math. 21 (1977), 429-490. | DOI | MR | JFM

[2] Appel, K., Haken, W.: Every planar map is four colorable. II. Reducibility. Ill. J. Math. 21 (1977), 491-567. | DOI | MR | JFM

[3] Borodin, O. V.: A proof of Grünbaum's conjecture on the acyclic 5-colorability of planar graphs. Dokl. Akad. Nauk SSSR 231 (1976), 18-20 Russian. | MR | JFM

[4] Borodin, O. V., Glebov, A. N.: On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph. Diskretn. Anal. Issled. Oper., Ser. 1 8 (2001), 34-53 Russian. | MR | JFM

[5] Borodin, O. V., Ivanova, A. O.: Near-proper vertex 2-colorings of sparse graphs. Diskretn. Anal. Issled. Oper. 16 (2009), 16-20 Russian. | MR | JFM

[6] Borodin, O. V., Kostochka, A. V.: Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1. Sib. Math. J. 52 (2011), 796-801. | DOI | MR | JFM

[7] Borodin, O. V., Kostochka, A. V.: Defective 2-colorings of sparse graphs. J. Comb. Theory, Ser. B 104 (2014), 72-80. | DOI | MR | JFM

[8] Chartrand, G., Kronk, H. V.: The point-arboricity of planar graphs. J. Lond. Math. Soc. 44 (1969), 612-616. | DOI | MR | JFM

[9] Chen, M., Raspaud, A., Wang, W.: Vertex-arboricity of planar graphs without intersecting triangles. Eur. J. Comb. 33 (2012), 905-923. | DOI | MR | JFM

[10] Chen, M., Yu, W., Wang, W.: On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree. Appl. Math. Comput. 326 (2018), 117-123. | DOI | MR | JFM

[11] Choi, H., Choi, I., Jeong, J., Suh, G.: $(1, k)$-coloring of graphs with girth at least five on a surface. J. Graph Theory 84 (2017), 521-535. | DOI | MR | JFM

[12] Choi, I., Raspaud, A.: Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Math. 338 (2015), 661-667. | DOI | MR | JFM

[13] Dross, F., Montassier, M., Pinlou, A.: Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. Eur. J. Comb. 66 (2017), 81-94. | DOI | MR | JFM

[14] Feghali, C., Šámal, R.: Decomposing a triangle-free planar graph into a forest and a subcubic forest. Eur. J. Comb. 116 (2024), Article ID 103878, 6 pages. | DOI | MR | JFM

[15] Havet, F., Sereni, J.-S.: Improper choosability of graphs and maximum average degree. J. Graph Theory 52 (2006), 181-199. | DOI | MR | JFM

[16] Kim, J., Kostochka, A., Zhu, X.: Improper coloring of sparse graphs with a given girth. I. (0,1)-colorings of triangle-free graphs. Eur. J. Comb. 42 (2014), 26-48. | DOI | MR | JFM

[17] Montassier, M., Ochem, P.: Near-colorings: Non-colorable graphs and NP-completeness. Electron. J. Comb. 22 (2015), Article ID P1.57, 13 pages. | DOI | MR | JFM

[18] Poh, K. S.: On the linear vertex-arboricity of a planar graph. J. Graph Theory 14 (1990), 73-75. | DOI | MR | JFM

[19] Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Comb. 29 (2008), 1064-1075. | DOI | MR | JFM

[20] Zhang, M., Chen, M., Wang, Y.: A sufficient condition for planar graphs with girth 5 to be (1,7)-colorable. J. Comb. Optim. 33 (2017), 847-865. | DOI | MR | JFM