Large Induced Forests in Planar Graphs
Planar graphs are graphs that can be drawn on a plane so that its edges do not cross each other (other that at their endpoints). In this thesis, we study the size of induced forests in planar graphs. The current best result by Borodin states that every planar graph has an induced forest that contains at least 2/5 of its vertices. In this thesis, we give partial results towards improving this bound. Specifically, we show that a minimal counterexample to an improved bound has minimal degree at least 3 and can contain only a specific type of vertices with degree 4.
Graduation Thesis language
Graduation Thesis type
Master - Computer Science
Dirk Oliver Theis, Kaveh Khoshkhah