题目: Induced forests in bipartite planar graphs

报告人：Yan WANG（Georgia Institute of Technology）

时间: 2015年5月25日, 周一 下午15:00-16:30

地点：管研楼1611

摘要： The Four-Color Theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a　common boundary do not share the same color. The　Four-Color Theorem was proved by using discharging method with the aid of　computer. Nowadays, discharging method is a standard technique to tackle planar graph problems.　In this talk, we will introduce the discharging method and then apply it to show that every simple bipartite planar graph on n vertices contains an induced forest on at least (4n+3)/7 vertices. This improves the best-known lower bound for Akiyama and Watanabe's conjecture (Every simple planar bipartite graph on n vertices contains an induced forest on at least 5n/8 vertices).