¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 317-322
A note on acyclic number of planar graphs*
Mirko Petrusevski
Department of Mathematics and Informatics, Faculty of Mechanical Engineering, Skopje, Republic of Macedonia
Riste Skrekovski
FMF, University ofLjubljana, Ljubljana Faculty of Information Studies, Novo mesto FAMNIT, University of Primorska, Koper, Slovenia
Received 31 May 2016, accepted 28 January 2017, published online 9 March 2017
Abstract
The acyclic number a(G) of a graph G is the maximum order of an induced forest in G.
The purpose of this short paper is to propose a conjecture that a(G) > - 20 n holds
for every planar graph G of girth g and order n, which captures three known conjectures on
the topic. In support of this conjecture, we prove a weaker result that a(G) > - n
holds. In addition, we give a construction showing that the constant § from the conjecture cannot be decreased.
Keywords: Induced forest, acyclic number, planar graph, girth. Math. Subj. Class.: 05C10, 05C15
1 Introduction
Throughout the paper n and g, respectively, stand for the order and girth of a (finite, simple, undirected) graph G. For other standard terminology and notation of graph theory we simply refer to [5]. The acyclic number of G, denoted a(G), is the maximum order of an induced forest in G. This parameter has been well investigated (see e.g. [1, 4, 9, 10]), and its determination is NP-hard even in the case of planar graphs [7]. In [2], Albertson and Berman proposed the following lower bound for it.
*We thank the referees for their helpful comments. This work is partially supported by ARRS Program P1-0383.
E-mail addresses: mirko.petrushevski@gmail.com (Mirko Petrusevski), skrekovski@gmail.com (Riste Skrekovski)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
318
Ars Math. Contemp. 13 (2017) 275-291
Conjecture 1.1. If G is a planar graph, then
n
a(G) > ^.
This conjecture has drawn much attention since it implies that every planar graph has a stable set on at least a quarter of its vertices, a fact known to be true only as a consequence of the Four Color Theorem. It holds for planar graphs of girth at least 4 as Salavatipour [10] (see also [4]) proved that a(G) > 17t>+24 whenever G is such a graph. The best known lower bound for a(G) over the class of all planar graphs G is the inequality a(G) > 2f, which can be readily deduced from the acyclic 5-colorability of planar graphs (proven by Borodin in [6]). A similar problem to Conjecture 1.1 is Conjecture 1.2 below, raised by Akiyama and Watanabe [1].
Conjecture 1.2. If G is a bipartite planar graph, then
a(G) > f.
Motivated by the last conjecture, the existence of large induced acyclic subgraphs in sparse bipartite graphs (resp. sparse graphs) was considered by Alon et al. in [3] (resp. [4]). Inspired by the fact that the dodecahedron attains the minimum possible ratio of order to size among all connected planar graphs of girth at least 5, Kowalik et al. [8] conjectured the following.
Conjecture 1.3. If G is a planar graph of girth g > 5, then
a(G) > —. ( ) > 10
The main purpose of this note is to generalize Conjectures 1.1, 1.2 and 1.3 through the following.
Conjecture 1.4. If G is a planar graph of girth g, then
a(G) > i1 - 2g)n
In particular, our conjecture reduces to Conjecture 1.1 (resp. Conjecture 1.3) for g = 3 (resp. g = 5), and for g = 4 strengthens Conjecture 1.2 by allowing odd 5+-cycles. Moreover, it suggests a lower bound a(G) > ^ if g > 6, a(G) > ht if g > 7 etc. Another way of stating Conjecture 1.4 is to claim that every non-acyclic planar graph G satisfies the inequality
a(G) 3
1 -— g . (1.1)
n J 2
Equivalently, we are looking for the smallest possible constant C, so that
1 - ^ ^ g < C,	(1.2)
holds for every planar graph of order n and finite girth g. If true, our conjecture is best possible in the sense that no excluding of a finite set of graphs could yield a better bound.
n
M. Petrusevski and R. Skrekovski: A note on acyclic number of planar graphs
319
Indeed, take a tree T and let K be K4, Q3 or the dodecahedron. For any graph G obtained by blowing up every vertex of T to a copy of K, (1.1) becomes an equality.
In support to Conjecture 1.4, in the next section we prove that C = 3 is sufficient for (1.2).
Theorem 1.5. If G is a planar graph of order n and girth g = g(G) < <x>, then
a(G) > - ^ n.	(1.3)
Moreover, for every integer g > 3 there exists a planar graph G of girth g for which
l(G) =
1 - I;"'
(1.4)
Notice that the first part of Theorem 1.5 implies Conjectures 1.1, 1.2, and 1.3, respectively, for girths g > 6, g > 8, and g > 10.
2 Proof of Theorem 1.5
The proof relies on an auxiliary result. Before stating it, let us recall some terminology. We use k-vertex and k+-vertex to refer to a vertex of degree k and a vertex of degree at least k, respectively. Given a plane graph G = (V, E), a face f is a region of R2\(V U |J E), and its length deg(f) is the degree of the corresponding vertex in the geometric dual G* (thus every bridge incident to f is counted twice in the length); we speak of an i-face f if deg(f) = i, and an i+-face is a face of length at least i. Recall that in case of a bridgeless plane graph, every cut-vertex is a 4+-vertex and for every face f it holds that deg(f) = |E(f)| (since its topological boundary d(f) is a union of simple curves). As usual, we say that a face f is incident with a vertex v if v e V ( f). Here is our auxiliary result.
Lemma 2.1. If G is a simple 2-edge-connected triangle-free plane graph with S(G) > 3, then there exists a face f e F(G) such that either:
(i)	f is a 4-face incident with at least one 3-vertex; or
(ii)	f is a 5-face incident with at least four distinct 3-vertices.
Proof. We use the discharging method. By the Euler formula, it holds that
^ (deg(v) - 4)+ ^ (deg(f) - 4) = -8,	(2.1)
veV(G)	f GF(G)
which leads to the following initial charge w0(x) for each x e V(G) U F(G):
w0(x) = deg(x) - 4.	(2.2)
By (2.1), the total charge is negative. On the other hand, (2.2) tells us that only the 3-vertices are with negative initial charge (equal to -1). Next, redistribute the initial charge according to the following simple rule:
(R) Every 5+-face sends a charge of 3 to each of its incident 3-vertices.
320
Ars Math. Contemp. 13 (2017) 275-291
Let w\ (x) denote the new charge of every x e V(G) U F(G) after applying (R). Assuming that a face satisfying (i) of Lemma 2.1 does not exist, for every v e V(G) it holds that wi(v) > 0 (since G is bridgeless, any 3-vertex lies on the boundary of three faces, thus receives a combined charge of 1). The fact that the total charge remains negative implies the existence of a face f with w1 (f) < 0. Moreover, from
0 > wi(f) > wo(f) - ^gf = |(deg(f) - 6),
it follows that every such f must be a 5-face incident with at least four 3-vertices. This completes the proof of the lemma.	□
Proof of Theorem 1.5. We show (1.3) by contradiction. Suppose G is a minimal (under inclusion) counter-example to (1.3) among all non-acyclic planar graphs. Then G is clearly connected, of finite girth g > 4 and A(G) > 3.
Claim 1: G is bridgeless. For otherwise, let e be a bridge and denote by G1; G2 the components of G - e. The choice of G combined with the fact that both subgraphs G1; G2 are of girth at least g, implies that a(Gj) > - | j n(Gj) for i = 1, 2. Summing up leads to the desired contradiction (1.3).
Le^G be a plane embedding of the graph obtained by suppressing every 2-vertex in G. Then G is bridgeless and ¿(G) > 3. Next we show that G meets all the requirements of Lemma 2.1.
Claim 2: G is simple and triangle-free. Supposing the opposite, there is a cycle C of G passing through at most three 3+-vertices. Denote by S the set of 2-vertices in V(C) and set s = |S|. In the graph G' = G - V(C), let M be amaximum acyclic set. Then MU S is an acyclic set of G, hence a(G) > a(G') + s. Combined with the choice of G, this would imply that
1 - f)<"- s - 3)+s< 0- £ which is equivalent to s + 3 < g. However, the last inequality contradicts that the length of C is at least g, and thus settles the claim.	_
Our aim of contradicting the existence of G is now achievable. Select an f e F(G) as in Lemma 2.1, and denote t = deg(f). For this choice of f we can certainly find an independent (seen in G) (t - 3)-subset T C V(f) consisting entirely of 3-vertices. Indeed, in case t = 4 the last assertion is trivial; as for t = 5, it is enough to consider four consecutive 3-vertices v1,v2, v3, v4 on f and observe that, by planarity, v1, v3 or v2,v4 form an independent pair.
Returning back to G, every boundary edge of f becomes a path of G whose interior consists entirely of 2-vertices. Let V2(f) be the collection of all 2-vertices lying on f, and denote r = |V2(f )|. Take from the graph G' = G - (V(f) U V2(f)) a maximum acyclic set M. Then M U V2 (F) U T is an acyclic set of G, giving that a(G) > a(G') + r +t - 3. Similarly to before, the last inequality would imply
1 - - )(n - r - + r + t - 3 < (1 - -
which is in turn equivalent to r +1 < g. The last inequality is clearly impossible and thus validates (1.3).
M. Petrusevski and R. Skrekovski: A note on acyclic number of planar graphs
321
Figure 1: Three cases for G (edges coming from M bolded) when k = 3.
In regard to the second assertion of Theorem 1.5, we provide a constructive proof based on the fact that the removal of any two vertices decycles K4: thus every subdivision of K4 with order n has acyclic number a = n — 2. Given an integer g > 3, it is of the form 3k + r where r equals either 0, 1 or 2. Construct the graph G as follows. Consider a copy of K4 and select a perfect matching M .If r = 0, then subdivide k — 1 times every e G E(K4); else if r = 1, then subdivide k times each e G M and every other edge k — 1 times; finally, if r = 2, then subdivide k — 1 times each e G M and every other edge k times (see Fig. 1). In either case the constructed subdivision G has the desired girth g. Moreover, as can be readily checked, its order n = 6k + 2(r — 1) and acyclic number a = 6k + 2(r — 2) satisfy
3 \	3
1	— T3 n = a — 1 + -,	(2.3) 2g g
since both sides of (2.3) are equal to (6k + 2r — 3)(3k + r	— 1)/(3k + r). Thus, it holds that
1—2g) nl.	(24)
Additionally, observe that for g = 3, (2.3) becomes equal	to a, which confirms that the
3
2	.
left-hand side of (1.2) is at least 2. This completes the proof of the theorem.	□
3 Concluding remarks and further work
We are fully aware that a technically more involved argument could lower the bound C < 3 in (1.2), however that was not our main objective.
References
[1]	J. Akiyama and M. Watanabe, Maximum induced forests of planar graphs, Graphs Combin. 3 (1987), 201-202, doi:10.1007/bf01788541.
[2]	M. O. Albertson and D. M. Berman, A conjecture on planar graphs, in: J. A. Bondy and U. S. R. Murty (eds.), Graph Theory and Related Topics, Academic Press, New York, p. 357, 1979, proceedings of the conference held in honour of Professor W. T. Tutte on the occasion of his sixtieth birthday.
[3]	N. Alon, Problems and results in extremal combinatorics—I, Discrete Math. 273 (2003), 3153, doi:10.1016/s0012-365x(03)00227-9.
[4]	N. Alon, D. Mubayi and R. Thomas, Large induced forests in sparse graphs, J. Graph Theory 38 (2001), 113-123, doi:10.1002/jgt.1028.
322
Ars Math. Contemp. 13 (2017) 275-291
[5]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
[6]	O. V. Borodin, A proof of B. Grunbaum's conjecture on the acyclic 5-colorability of planar graphs, Dokl. Akad. Nauk SSSR 231 (1976), 18-20.
[7]	R. M. Karp, Reducibility among combinatorial problems, in: R. E. Miller, J. W. Thatcher and J. D. Bohlinger (eds.), Complexity of Computer Computations, Plenum Press, New York, The IBM Research Symposia Series, pp. 85-103, 1972, doi:10.1007/978-1-4684-2001-2.9.
[8]	L. Kowalik, B. LuZar and R. Skrekovski, An improved bound on the largest induced forests for triangle-free planar graphs, Discrete Math. Theor. Comput. Sci. 12 (2010), 87-100, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/ view/1323/0.html.
[9]	N. Punnim, The decycling number of regular graphs, Thai J. Math. 4 (2006), 145-161, http: //thaijmath.in.cmu.ac.th/index.php/thaijmath/article/view/67.
[10] M. R. Salavatipour, Large induced forests in triangle-free planar graphs, Graphs Combin. 22 (2006), 113-126, doi:10.1007/s00373-006-0642-7.