Large Induced Forests in Planar Graphs
Name
Kairi Hennoch
Abstract
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
English
Graduation Thesis type
Master - Computer Science
Supervisor(s)
Dirk Oliver Theis, Kaveh Khoshkhah
Defence year
2016