Geodesic
The decycling number of a planar graph covered by $K_4$-subgraphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 459-473 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G be a planar graph of n vertices. The paper shows that the decycling number of G is at most n-12 if G has not any K_4-minor. If the maximum degree of G is at most four and G is not 4-regular, the paper proves that the decycling number of G is n2 if and only if G is covered by K_4-subgraphs. In addition, the decycling number of G covered by octahedron-subgraphs or icosahedron-subgraphs is studied.
Keywords: decycling number, planar graph, $K_4$-minor 
@article{DMGT_2024_44_2_a2,
     author = {Ma, Dengju and Ma, Mingyuan and Ren, Han},
     title = {The decycling number of a planar graph covered by $K_4$-subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {459--473},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a2/}
}
TY  - JOUR
AU  - Ma, Dengju
AU  - Ma, Mingyuan
AU  - Ren, Han
TI  - The decycling number of a planar graph covered by $K_4$-subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 459
EP  - 473
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a2/
LA  - en
ID  - DMGT_2024_44_2_a2
ER  - 
%0 Journal Article
%A Ma, Dengju
%A Ma, Mingyuan
%A Ren, Han
%T The decycling number of a planar graph covered by $K_4$-subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 459-473
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a2/
%G en
%F DMGT_2024_44_2_a2
Ma, Dengju; Ma, Mingyuan; Ren, Han. The decycling number of a planar graph covered by $K_4$-subgraphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 459-473. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a2/

[1] M.O. Albertson and D.M Berman, The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XVII (1976) 51–69.

[2] L.W. Beineke and R.C. Vandell, Decycling graphs, J. Graph Theory 25 (1997) 59–77. https://doi.org/10.1002/(SICI)1097-0118(199705)25:13.0.CO;2-H

[3] J.A. Bondy and U.S.R.Murty, Graph Theory (Springer, 2008).

[4] O.V. Borodin, A proof of Grüngaum's conjecture on the acyclic 5-colorability of planar graphs, Dokl. Akad. Nauk SSSR 231 (1976) 18–20, in Russian.

[5] P. Erdős, M. Saks and V. Sós, Maximum induced trees in graphs, J. Combin. Theory Ser. B 41 (1986) 61–79. https://doi.org/10.1016/0095-8956(86)90028-6

[6] P. Festa, P.M. Pardalos and M.G.C. Reseude, Feedback set problem, in: Handbook of Combinatorial Optimization, Supplement Vol. A, (Kluwer, Dordrecht 1999) 209–258.

[7] K. Hosono, Induced forests in trees and outerplanar graphs, Proc. Fac. Sci. Tokai Univ. 25 (1990) 27–29.

[8] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller, J.W. Thatcher, J.D. Bohlinger (Ed(s)), (The IBM Research Symposia Series Springer, Boston, MA 1972) 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9

[9] J.P. Liu and C. Zhao, A new bound on the feedback vertex sets in cubic graphs, Discrete Math. 184 (1996) 119–131. https://doi.org/10.1016/0012-365X(94)00268-N

[10] S.D. Long and H. Ren, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018) 375–384. https://doi.org/10.1002/jgt.22218

[11] D.A. Pike and Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005) 651–663. https://doi.org/10.1137/S089548010444016X

[12] N. Punnim, The decycling number of regular graphs, Thai J. Math. 4 (2006) 145–161.

[13] H. Ren, C. Yang and T.-X. Zhao, A new formula for the decycling number of regular graphs, Discrete Math. 340 (2017) 3020–3031. https://doi.org/10.1016/j.disc.2017.07.011

[14] A.T. White, Graphs, Groups and Surfaces (North-Holland, 1973).

[15] H. Whitney, Two-isomorphic graphs, Trans. Amer. Math. Soc. 34 (1932) 339–362. https://doi.org/10.1090/S0002-9947-1932-1501641-2