Event Type:

Number Theory Seminar

Date/Time:

Tuesday, May 5, 2015 - 16:00 to 17:00

Location:

Bat 150

Guest Speaker:

Institution:

School of EECS, OSU

Abstract:

We show that every graph has an induced pseudoforest of at least n−m/4.5 vertices, an induced partial 2-tree of at least n−m/5 vertices, and an induced planar subgraph of at least n−m/5.2174 vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest Kh-minor-free graph in a given graph can sometimes be at most n−m/6+o(m).