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

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

Czechoslovak Mathematical Journal (2024)

  • Volume: 74, Issue: 2, page 355-366
  • ISSN: 0011-4642

Abstract

top
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 Δ ( G [ V 1 ] ) ≤ d 1 and Δ ( G [ V 2 ] ) ≤ d 2 , then we say G has a ( Δ d 1 , Δ 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.

How to cite

top

Chen, Min, et al. "Partitioning planar graph of girth 5 into two forests with maximum degree 4." Czechoslovak Mathematical Journal 74.2 (2024): 355-366. <http://eudml.org/doc/299335>.

@article{Chen2024,
abstract = {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.},
author = {Chen, Min, Raspaud, André, Wang, Weifan, Yu, Weiqiang},
journal = {Czechoslovak Mathematical Journal},
keywords = {vertex partition; girth; forest; maximum degree},
language = {eng},
number = {2},
pages = {355-366},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Partitioning planar graph of girth 5 into two forests with maximum degree 4},
url = {http://eudml.org/doc/299335},
volume = {74},
year = {2024},
}

TY - JOUR
AU - Chen, Min
AU - Raspaud, André
AU - Wang, Weifan
AU - Yu, Weiqiang
TI - Partitioning planar graph of girth 5 into two forests with maximum degree 4
JO - Czechoslovak Mathematical Journal
PY - 2024
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 74
IS - 2
SP - 355
EP - 366
AB - 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.
LA - eng
KW - vertex partition; girth; forest; maximum degree
UR - http://eudml.org/doc/299335
ER -

References

top
  1. Appel, K., Haken, W., 10.1215/ijm/1256049011, Ill. J. Math. 21 (1977), 429-490. (1977) Zbl0387.05009MR0543792DOI10.1215/ijm/1256049011
  2. Appel, K., Haken, W., 10.1215/ijm/1256049012, Ill. J. Math. 21 (1977), 491-567. (1977) Zbl0387.05010MR0543793DOI10.1215/ijm/1256049012
  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. (1976) Zbl0363.05031MR0447031
  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. (2001) Zbl1012.05133MR1918259
  5. Borodin, O. V., Ivanova, A. O., Near-proper vertex 2-colorings of sparse graphs, Diskretn. Anal. Issled. Oper. 16 (2009), 16-20 Russian. (2009) Zbl1249.05110MR2574306
  6. Borodin, O. V., Kostochka, A. V., 10.1134/S0037446611050041, Sib. Math. J. 52 (2011), 796-801. (2011) Zbl1232.05073MR2908122DOI10.1134/S0037446611050041
  7. Borodin, O. V., Kostochka, A. V., 10.1016/j.jctb.2013.10.002, J. Comb. Theory, Ser. B 104 (2014), 72-80. (2014) Zbl1282.05041MR3132745DOI10.1016/j.jctb.2013.10.002
  8. Chartrand, G., Kronk, H. V., 10.1112/jlms/s1-44.1.612, J. Lond. Math. Soc. 44 (1969), 612-616. (1969) Zbl0175.50505MR0239996DOI10.1112/jlms/s1-44.1.612
  9. Chen, M., Raspaud, A., Wang, W., 10.1016/j.ejc.2011.09.017, Eur. J. Comb. 33 (2012), 905-923. (2012) Zbl1250.05062MR2889524DOI10.1016/j.ejc.2011.09.017
  10. Chen, M., Yu, W., Wang, W., 10.1016/j.amc.2018.01.003, Appl. Math. Comput. 326 (2018), 117-123. (2018) Zbl1426.05114MR3759461DOI10.1016/j.amc.2018.01.003
  11. Choi, H., Choi, I., Jeong, J., Suh, G., 10.1002/jgt.22039, J. Graph Theory 84 (2017), 521-535. (2017) Zbl1359.05099MR3623392DOI10.1002/jgt.22039
  12. Choi, I., Raspaud, A., 10.1016/j.disc.2014.11.012, Discrete Math. 338 (2015), 661-667. (2015) Zbl1305.05072MR3300755DOI10.1016/j.disc.2014.11.012
  13. Dross, F., Montassier, M., Pinlou, A., 10.1016/j.ejc.2017.06.014, Eur. J. Comb. 66 (2017), 81-94. (2017) Zbl1369.05169MR3692138DOI10.1016/j.ejc.2017.06.014
  14. Feghali, C., Šámal, R., 10.1016/j.ejc.2023.103878, Eur. J. Comb. 116 (2024), Article ID 103878, 6 pages. (2024) Zbl07799827MR4666807DOI10.1016/j.ejc.2023.103878
  15. Havet, F., Sereni, J.-S., 10.1002/jgt.20155, J. Graph Theory 52 (2006), 181-199. (2006) Zbl1104.05026MR2230831DOI10.1002/jgt.20155
  16. Kim, J., Kostochka, A., Zhu, X., 10.1016/j.ejc.2014.05.003, Eur. J. Comb. 42 (2014), 26-48. (2014) Zbl1297.05083MR3240135DOI10.1016/j.ejc.2014.05.003
  17. Montassier, M., Ochem, P., 10.37236/3509, Electron. J. Comb. 22 (2015), Article ID P1.57, 13 pages. (2015) Zbl1308.05052MR3336571DOI10.37236/3509
  18. Poh, K. S., 10.1002/jgt.3190140108, J. Graph Theory 14 (1990), 73-75. (1990) Zbl0705.05016MR1037422DOI10.1002/jgt.3190140108
  19. Raspaud, A., Wang, W., 10.1016/j.ejc.2007.11.022, Eur. J. Comb. 29 (2008), 1064-1075. (2008) Zbl1144.05024MR2408378DOI10.1016/j.ejc.2007.11.022
  20. Zhang, M., Chen, M., Wang, Y., 10.1007/s10878-016-0010-3, J. Comb. Optim. 33 (2017), 847-865. (2017) Zbl1367.05054MR3619509DOI10.1007/s10878-016-0010-3

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.