- Series
- Graph Theory Working Seminar
- Time
- Thursday, March 5, 2020 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Joshua Schroeder – Georgia Tech
- Organizer
- Joshua Schroeder and Xingxing Yu
In 1980, Wagon showed that $\chi(G) \leq f_m(n)$ for any $\{mK_2, K_n\}$-free graph $G$, where $f_m$ is a polynomial and $mK_2$ is an induced matching of size $m$. However this bound is not known to be sharp. Recently, Gaspers and Huang helped sharpen this bound by showing for any $\{2K_2, K_4\}$-free graph $G$, that $\chi(G) \leq 4$. This resolves the question raised by Wagon for $m=2$, $n=4$. For the case where $m = 3$, it was shown by Brandt in 2002 that $(K_3, 3K_2)$-free graphs are 4-colorable. In this talk, I will provide the outline for an alternate proof of this fact, as a byproduct of my research project.