{"id":"arxiv/2605.08848","url":"https://arxiv.org/abs/2605.08848","tags":["math.CO"],"score":0,"title":"Ramsey-type $χ$-bounds for $χ$-bounded graph classes","domain":"math.CO","source":"arxiv","authors":["Tung Nguyen","Sang-il Oum"],"reviews":0,"subject":"math.CO","summary":"We prove that for every path $P$, the class of graphs with no induced $P$ and no induced four-cycle $C_4$ 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 \\cdot R(α(H),ω(G)+1)$ for some constant $C$ depending only on $T$ and $H$, where $R(\\cdot,\\cdot)$ denotes the usual Ramsey numbers. We show that this holds in the following two instances, which strengthen the case $T=P$ and $H=C_4$ mentioned above: (1) every…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-09","reactions":{}}