### Two graph classes with bounded chromatic number

- Series
- Dissertation Defense
- Time
- Monday, April 17, 2023 - 09:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 114 (or Zoom)
- Speaker
- Joshua Schroeder – Georgia Tech – jschroeder35@gatech.edu

Zoom: https://gatech.zoom.us/j/98256586748?pwd=SkJLZ3ZKcjZsM0JkbGdyZ1Y3Tk9udz0... />

Meeting ID: 982 5658 6748<br />

Password: 929165

A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic $\chi$-binding function. In addition to confirming that chair-free graphs admit a quadratic $\chi$-binding function, we will extend the result by demonstrating that $t$-broom free graphs are polynomially $\chi$-bounded for any $t$ with binding function $f(\omega) = O(\omega^{t+1})$. A class of graphs is said to satisfy the Vizing bound if it admits the $\chi$-binding function $f(\omega) = \omega + 1$. It was conjectured that (fork, $K_3$)-free graphs would be 3-colorable, where fork is the graph obtained from $K_{1, 4}$ by subdividing two edges. This would also imply that (paw, fork)-free graphs satisfy the Vizing bound. We will prove this conjecture through a series of lemmas that constrain the structure of any minimal counterexample.