Polynomial $\chi$-binding functions for $t$-broom-free graphs
- Series
- Graph Theory Seminar
- Time
- Tuesday, September 7, 2021 - 15:45 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Joshua Schroeder – Georgia Institute of Technology – jschroeder35@gatech.edu
For any positive integer t, a t-broom is a graph obtained from K1,t+1 by subdividing an edge once. In this paper, we show that, for graphs G without induced t-brooms, we have χ(G)=o(ω(G)t+1), where χ(G) and ω(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 χ(G) to 7.5ω(G)2, confirming a conjecture of Sivaraman. For t≥3 and {t-broom, Kt,t}-free graphs, we improve the bound to o(ωt−1+2t+1). Joint work with Xiaonan Liu, Zhiyu Wang, and Xingxing Yu.