{"id":"arxiv/2608.02522","url":"https://arxiv.org/abs/2608.02522","tags":["math.CO"],"score":0,"title":"Locally bipartite subgraphs via multicolor Ramsey numbers","domain":"math.CO","source":"arxiv","authors":["Raphael Steiner"],"reviews":0,"subject":"math.CO","summary":"A famous conjecture of Erdős and Hajnal (1969) states that for every integer $g\\ge 4$ there is a smallest function $f_g:\\mathbb{N}\\to\\mathbb{N}$ such that every graph of chromatic number at least $f_g(k)$ contains a subgraph of chromatic number $k$ and girth at least $g$. So far, this has only been proved for $g=4$ by Rödl (1977), with $f_4(k)$ bounded by a tower of height $Θ(k^2\\log k)$. We exhibit a surprising connection between finding high-chromatic subgraphs of large odd-girth (avoiding short odd cycles) and lower-bounding multicolor Ramsey numbers of odd cycles. Using this connection,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-03","reactions":{}}