Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
vertex partition; girth; forest; maximum degree
vertex partition; girth; forest; maximum degree
Summary:
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.
References:
[1] Appel, K., Haken, W.: Every planar map is four colorable. I. Discharging. Ill. J. Math. 21 (1977), 429-490. DOI 10.1215/ijm/1256049011 | MR 0543792 | Zbl 0387.05009
[2] Appel, K., Haken, W.: Every planar map is four colorable. II. Reducibility. Ill. J. Math. 21 (1977), 491-567. DOI 10.1215/ijm/1256049012 | MR 0543793 | Zbl 0387.05010
[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 0447031 | Zbl 0363.05031
[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 1918259 | Zbl 1012.05133
[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 2574306 | Zbl 1249.05110
[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 10.1134/S0037446611050041 | MR 2908122 | Zbl 1232.05073
[7] Borodin, O. V., Kostochka, A. V.: Defective 2-colorings of sparse graphs. J. Comb. Theory, Ser. B 104 (2014), 72-80. DOI 10.1016/j.jctb.2013.10.002 | MR 3132745 | Zbl 1282.05041
[8] Chartrand, G., Kronk, H. V.: The point-arboricity of planar graphs. J. Lond. Math. Soc. 44 (1969), 612-616. DOI 10.1112/jlms/s1-44.1.612 | MR 0239996 | Zbl 0175.50505
[9] Chen, M., Raspaud, A., Wang, W.: Vertex-arboricity of planar graphs without intersecting triangles. Eur. J. Comb. 33 (2012), 905-923. DOI 10.1016/j.ejc.2011.09.017 | MR 2889524 | Zbl 1250.05062
[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 10.1016/j.amc.2018.01.003 | MR 3759461 | Zbl 1426.05114
[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 10.1002/jgt.22039 | MR 3623392 | Zbl 1359.05099
[12] Choi, I., Raspaud, A.: Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Math. 338 (2015), 661-667. DOI 10.1016/j.disc.2014.11.012 | MR 3300755 | Zbl 1305.05072
[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 10.1016/j.ejc.2017.06.014 | MR 3692138 | Zbl 1369.05169
[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 10.1016/j.ejc.2023.103878 | MR 4666807 | Zbl 07799827
[15] Havet, F., Sereni, J.-S.: Improper choosability of graphs and maximum average degree. J. Graph Theory 52 (2006), 181-199. DOI 10.1002/jgt.20155 | MR 2230831 | Zbl 1104.05026
[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 10.1016/j.ejc.2014.05.003 | MR 3240135 | Zbl 1297.05083
[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 10.37236/3509 | MR 3336571 | Zbl 1308.05052
[18] Poh, K. S.: On the linear vertex-arboricity of a planar graph. J. Graph Theory 14 (1990), 73-75. DOI 10.1002/jgt.3190140108 | MR 1037422 | Zbl 0705.05016
[19] Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Comb. 29 (2008), 1064-1075. DOI 10.1016/j.ejc.2007.11.022 | MR 2408378 | Zbl 1144.05024
[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 10.1007/s10878-016-0010-3 | MR 3619509 | Zbl 1367.05054
Search
Partner of
