2026/05/09 by Tung Nguyen, Sang-il Oum · 1 voice
Mathematics · #math.CO
We prove that for every path P, the class of graphs with no induced P and no induced four-cycle C4 is linearly χ-bounded. More generally, we ask for which pairs \T,H\ where T is a forest and H is a complete multipartite graph, every graph G with no induced T and no induced H has chromatic number at most C ⋅ R(α(H),ω(G)+1) for some constant C depending only on T and H, where R(⋅,⋅) denotes the usual Ramsey numbers. We show that this holds in the following two instances, which strengthen the case T=P and H=C4 mentioned above: (1) every component of T is a broom and H is complete multipartite; or (2) T is a forest and H is complete bipartite. These two unify and substantially extend a number of previous results on linear and polynomial χ-boundedness for various graph classes. For case (2), we also provide a new proof (with better bounds) of a recent result of Fox, Nenadov, and Pham on the existence of an induced copy of a fixed tree in a graph satisfying certain sparsity conditions.