Georgia Institute of Technology College of Sciences

For any positive integer $t$, a $t$-broom is a graph obtained from $K_{1,t+1}$ by subdividing an edge once.  In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $\chi(G) =  o(\omega(G)^{t+1})$, where  $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of  Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $\chi(G)$ to $7.5\omega(G)^2$, confirming a conjecture of Sivaraman. For $t\geq 3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(\omega^{t-1+\frac{2}{t+1}})$. Joint work with Xiaonan Liu, Zhiyu Wang, and Xingxing Yu.