Article in volume
Authors:
Title:
The decycling number of a graph with large girth embedded in a surface
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 595-614
Received: 2023-11-21 , Revised: 2024-04-17 , Accepted: 2024-04-17 , Available online: 2024-06-14 , https://doi.org/10.7151/dmgt.2547
Abstract:
It were conjectured that the decycling number of a bipartite planar graph of
$n$ vertices is at most $\frac{3n}{8}$, and that the decycling number of a
planar graph of $n$ vertices with girth at least five is at most $\frac{3n}{10}$.
In this paper we show that the decycling number of a planar graph of $n$
vertices with girth at least six (or eight) is at most $\frac{3n-6}{8}$ (or
$\frac{3n-6}{10}$), which means that the first conjecture is true if the girth
is at least six and the second conjecture holds if the girth is at least eight.
If $G$ is a connected graph $2$-cell embedded in the orientable surface
$S_{\gamma} (\gamma\geq 1)$, we prove that the decycling number of $G$ is at
most $\frac{3}{8}(n-2+2\gamma)$ (or $\frac{3}{10}(n-2+2\gamma)$) if the girth
of $G$ is at least $6+4\gamma$ (or $8+6\gamma$). Similarly, if $G$ is $2$-cell
embedded in the non-orientable surface $N_{\bar\gamma}$, then the decycling
number of $G$ is at most $\frac{3}{8} (n-2+\bar\gamma)$ (or
$\frac{3}{10}(n-2+\bar\gamma)$) if the girth of $G$ is at least $6+2\bar\gamma$
(or $8+4\bar\gamma$).
Keywords:
decycling number, girth, embedding
References:
- J. Akiyama and M. Watanabe, Maximum induced forests of planar graphs, Graphs Combin. 3 (1987) 201–202.
https://doi.org/10.1007/BF01788541 - M.O. Albertson and R.Haas, A problem raised at the DIMACS Graph Coloring Week (New Jersey, 1998).
- M.O Albertson and D.M. Berman, The acyclic chromatic number, in: Proc. Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congr. Number. 17, (Vinnipeg, Man., 1976) 51–69.
- N. Alon, Problems and results in extremal combinatorics–-I, Discrete Math. 273 (2003) 31–53.
https://doi.org/10.1016/S0012-365X(03)00227-9 - N. Alon, D. Mubayi and R. Thomas, Large induced forests in sparse graphs, J. Graph Theory 38 (2001) 113–123.
https://doi.org/10.1002/jgt.1028 - 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:1<59::AID-JGT4>3.0.CO;2-H - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - B. Bollobás, Extremal Graph Theory (Academic Press, London-NewYork-San Francisco, 1978).
- O.V. Borodin, A proof of Grünbaum's conjecture on the acyclic $5$-colorability of planar graphs, Dokl. Akad. Nauk SSSR 231 (1976) 18–20, in Russian.
- F. Dross, M. Montassier and A. Pinlou, A lower bound on the order of the largest induced forest in planar graphs with high girth, Discrete Appl. Math. 214 (2016) 99–107.
https://doi.org/10.1016/j.dam.2016.06.011 - F. Dross, M. Montassier and A. Pinlou, Large induced forests in planar graphs with girth $4$, Discrete Appl. Math. 254 (2019) 96–106.
https://doi.org/10.1016/j.dam.2018.06.029 - P. Erdős, M. Saks and V.T. 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 - P. Festa, P.M. Pardalos and M.G.C. Reseude, Feedback set problem, in: Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos (Ed(s)), (Springer, Boston, MA 1999) 209–258.
https://doi.org/10.1007/978-1-4757-3023-4_4 - P.J. Heahood, Map-colour theorem, Quart. J. Pure and Appl. Math. 24 (1890) 332–338.
- K. Hosono, Induced forests in trees and outerplanar graphs, Proc. Fac. Sci. Tokai Univ. 25 (1990) 27–29.
- R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller, J.W. Thatcher and J.D. Bohlinger (Ed(s)), (Springer, Boston, MA 1972) 85–103.
https://doi.org/10.1007/978-1-4684-2001-2_9 - L. Kowalik, B. Lužar and R. Škrekovski, An improved bound on the large induced forests for triangle-free planar graphs, Discrete Math. Theor. Comput. Sci. 12 (2010) 87–100.
https://doi.org/10.46298/dmtcs.487 - J.-P. Liu and C. Zhao, A new bound on the feedback vertex sets in cubic graphs, Discrete Math. 148 (1996) 119–131.
https://doi.org/10.1016/0012-365X(94)00268-N - 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 - M.-Y. Ma and H. Ren, The decycling number of a line graph, (2024) a manuscript, submitted.
- B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, 2001).
https://doi.org/10.56021/9780801866890 - 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 - 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 - G. Ringel, Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg 28 (1965) 139–150.
https://doi.org/10.1007/BF02993245 - G. Ringel, Der vollständige paare Graph auf nichtorientierbaren Flächen, J. Reine Angew. Math. 220 (1965) 88–93.
https://doi.org/10.1515/crll.1965.220.88
Close