DMS Combinatorics Seminar

Speaker: Zhiyu Wang (Louisiana State University)

Title: An improved \(\chi\)-binding function for chair-free graphs

Abstract: We show that if a graph \(G\) does not contain the chair (the graph obtained from \(K_{1,3}\) by subdividing an edge once) as an induced subgraph, then its chromatic number satisfies \(\chi(G) \leq \omega(G)^2\), where \(\chi(G)\) and \(\omega(G)\) denote the chromatic number and clique number of \(G\), respectively. This result improves the recent upper bound of \(7\omega(G)^2\) proved by Liu, Schroeder, Wang, and Yu [J. Combin. Theory Ser. B 162 (2021) 118—133].

This is joint work with Weihao Xia.