Maximum acyclic and fragmented sets in regular graphs
Penny E. Haxell, Oleg Pikhurko, Andrew G. Thomason · Journal of Graph Theory · 2007
Abstract We show that a typical d‐regular graph G of order n does not contain an induced forest with around ${2 {\rm In} d \over d}$ vertices, when n ≫ d ≫ 1, this bound being best possible because of a result of Frieze and Łuczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008