Large induced forests in sparse graphs (Q2781059)

A set \(S\) of vertices of a (simple, undirected) graph \(G\) is acyclic if \(G[S]\), the subgraph it spans, is a forest; \(a(G)\) denotes the maximum cardinality of an acyclic set in \(G\). \(\dot K_4\) is the graph obtained from \(K_4\) by subdividing an edge; \({\mathcal F}(t,k)\) denotes the family of connected graphs with maximum degree 3 obtained by adding edges to the disjoint union of \(t\) triangles and \(k\) copies of \(\dot K_4\) so that the multigraph obtained by contracting each triangle and each copy of \(\dot K_4\) to a single vertex is a tree of order \(t+k\) (without multiple edges); \({\mathcal F}\) is the union of all \({\mathcal F}(t,k)\) where \(t\) and \(k\) take on all non-negative values such that \(t+k>0\). A lower bound for \(a(G)\) is known from \textit{N. Alon, J. Kahn} and \textit{P. D. Seymour} [Large induced degenerate subgraphs, Graphs Comb. 3, 203-211 (1987; Zbl 0624.05039)]. NEWLINENEWLINENEWLINEThis paper was motivated by a conjecture of M. Albertson and R. Haas: If \(G\) is an \(n\)-vertex planar bipartite graph, then \(a(G)\geq\frac 58n\). The authors begin by proving Lemma 2.1: If \(G=(V,E)\) is a triangle-free graph, then \(a(G)\geq |V|-\frac {|E|}4\). Theorem 1.5: If exactly \(c\) components of a \(K_4\)-free graph \(G\) with maximum degree 3 are from \({\mathcal F}\), then \(a(G)\geq|V|-\frac{|E|}4-\frac c4\). Corollary 1.7: If \(G\) is an \(n\)-vertex triangle-free graph with maximum degree 3, then \(a(G)\geq\frac{5n}8\), and the inequality is sharp whenever \(8|n\). Theorem 1.7: Let \(G=(V,E)\) be a connected graph with maximum degree \(\Delta\geq 3\). Then \(a(G)\geq\alpha(G)+\frac{|V|-\alpha(G)}{(\Delta-1)^2}\) (where \(\alpha\) denotes the independence number). In \S 4 the authors construct \(n\)-vertex \(\Delta\)-regular bipartite graphs \(G_{a,b}\) (where \(ab=n\)) with \(a(G)\leq \frac n2+{\mathcal O}(\frac n{\Delta^2})\) as \(n\to\infty\). Theorem 4.3: \(a(G_{a,b})\leq ab+1\). Corollary 4.4: For integers \(\Delta\), \(n\), where \(\left\lfloor(\Delta+1)^2/2\right\rfloor|n\), there exists an \(n\)-vertex \(\Delta\)-regular bipartite graph with \(a(G)=\frac n2+\frac{n}{\lfloor\frac{(\Delta+1)^2}2\rfloor}\). If \((2\Delta)|n\), then there exists an \(n\)-vertex \(\Delta\)-regular bipartite graph with \(a(G)=\frac n2+\frac n{2\Delta}\). Remark 4.5: The graphs \(G_{a,b}\) also provide our best constructions for 4-regular and 5-regular bipartite graphs with no large acyclic sets. In particular, Theorem 4.3 immediately yields \(a(G_{2,3})=7\), and \(a(G_{3,3})=10\).