| 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 |
| idZBL:
|
Zbl 07893385 |
| idMR:
|
MR4764526 |
| DOI:
|
10.21136/CMJ.2024.0394-21 |
| . |
| Date available:
|
2024-07-10T14:48:27Z |
| Last updated:
|
2026-07-06 |
| 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 |
| . |
