Locally bipartite subgraphs via multicolor Ramsey numbers
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02522
curl -X POST /api/v1/records/arxiv/2608.02522/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02522/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'