Polynomial $\chi$-binding functions for $t$-broom-free graphs

Abstract

For any positive integer $t$, a \emph{$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\omega (G{)}^2$, confirming a conjecture of Sivaraman. For $t\ge 3$ and \{$t$-broom, $K_{t,t}$\}-free graphs, we improve the bound to $o({\omega }^t)$.

14 pages, 1 figure