(2P2, K4)-Free Graphs are 4-Colorable

Graph Theory Working Seminar
Wednesday, October 31, 2018 - 4:30pm
1 hour (actually 50 minutes)
Skiles 006
Georgia Tech
A graph G is H-free if H is not isomorphic to an induced subgraph of G. Let Pt denote the path on t vertices, and let Kn denote the complete graph on n vertices. For a positive integer r, we use rG to denote the disjoint union of r copies of G. In this talk, we will discuss the result, by Gaspers and Huang, that (2P2, K4)-free graphs are 4-colorable, where the bound is attained by the five-wheel and the complement of seven-cycle. It answers an open question by Wagon in 1980s.