Article
| Title: | Partitioning planar graph of girth 5 into two forests with maximum degree 4 (English) |
| Author: | Chen, Min |
| Author: | Raspaud, André |
| Author: | Wang, Weifan |
| Author: | Yu, Weiqiang |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 74 |
| Issue: | 2 |
| Year: | 2024 |
| Pages: | 355-366 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | vertex partition |
| Keyword: | girth |
| Keyword: | forest |
| Keyword: | maximum degree |
| MSC: | 05C10 |
| MSC: | 05C69 |
| DOI: | 10.21136/CMJ.2024.0394-21 |
| . | |
| Date available: | 2024-07-10T14:48:27Z |
| Last updated: | 2024-07-15 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/152443 |
| . | |
| Reference: | [1] Appel, K., Haken, W.: Every planar map is four colorable. I. Discharging.Ill. J. Math. 21 (1977), 429-490. Zbl 0387.05009, MR 0543792, 10.1215/ijm/1256049011 |
| Reference: | [2] Appel, K., Haken, W.: Every planar map is four colorable. II. Reducibility.Ill. J. Math. 21 (1977), 491-567. Zbl 0387.05010, MR 0543793, 10.1215/ijm/1256049012 |
| Reference: | [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. Zbl 0363.05031, MR 0447031 |
| Reference: | [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. Zbl 1012.05133, MR 1918259 |
| Reference: | [5] Borodin, O. V., Ivanova, A. O.: Near-proper vertex 2-colorings of sparse graphs.Diskretn. Anal. Issled. Oper. 16 (2009), 16-20 Russian. Zbl 1249.05110, MR 2574306 |
| Reference: | [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. Zbl 1232.05073, MR 2908122, 10.1134/S0037446611050041 |
| Reference: | [7] Borodin, O. V., Kostochka, A. V.: Defective 2-colorings of sparse graphs.J. Comb. Theory, Ser. B 104 (2014), 72-80. Zbl 1282.05041, MR 3132745, 10.1016/j.jctb.2013.10.002 |
| Reference: | [8] Chartrand, G., Kronk, H. V.: The point-arboricity of planar graphs.J. Lond. Math. Soc. 44 (1969), 612-616. Zbl 0175.50505, MR 0239996, 10.1112/jlms/s1-44.1.612 |
| Reference: | [9] Chen, M., Raspaud, A., Wang, W.: Vertex-arboricity of planar graphs without intersecting triangles.Eur. J. Comb. 33 (2012), 905-923. Zbl 1250.05062, MR 2889524, 10.1016/j.ejc.2011.09.017 |
| Reference: | [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. Zbl 1426.05114, MR 3759461, 10.1016/j.amc.2018.01.003 |
| Reference: | [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. Zbl 1359.05099, MR 3623392, 10.1002/jgt.22039 |
| Reference: | [12] Choi, I., Raspaud, A.: Planar graphs with girth at least 5 are (3,5)-colorable.Discrete Math. 338 (2015), 661-667. Zbl 1305.05072, MR 3300755, 10.1016/j.disc.2014.11.012 |
| Reference: | [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. Zbl 1369.05169, MR 3692138, 10.1016/j.ejc.2017.06.014 |
| Reference: | [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. Zbl 07799827, MR 4666807, 10.1016/j.ejc.2023.103878 |
| Reference: | [15] Havet, F., Sereni, J.-S.: Improper choosability of graphs and maximum average degree.J. Graph Theory 52 (2006), 181-199. Zbl 1104.05026, MR 2230831, 10.1002/jgt.20155 |
| Reference: | [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. Zbl 1297.05083, MR 3240135, 10.1016/j.ejc.2014.05.003 |
| Reference: | [17] Montassier, M., Ochem, P.: Near-colorings: Non-colorable graphs and NP-completeness.Electron. J. Comb. 22 (2015), Article ID P1.57, 13 pages. Zbl 1308.05052, MR 3336571, 10.37236/3509 |
| Reference: | [18] Poh, K. S.: On the linear vertex-arboricity of a planar graph.J. Graph Theory 14 (1990), 73-75. Zbl 0705.05016, MR 1037422, 10.1002/jgt.3190140108 |
| Reference: | [19] Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs.Eur. J. Comb. 29 (2008), 1064-1075. Zbl 1144.05024, MR 2408378, 10.1016/j.ejc.2007.11.022 |
| Reference: | [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. Zbl 1367.05054, MR 3619509, 10.1007/s10878-016-0010-3 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
