Dense induced bipartite subgraphs under local sparsity
Source: arxiv.org/abs/2611.26277
The study of dense induced bipartite subgraphs dates back to the work of Erdős, Faudree, Pach, and Spencer on triangle-free graphs. In this paper, we study this problem under different local sparsity conditions. First, we prove that for every fixed integer $t\ge 2$ and all sufficiently large $d$, every $K_{t,t}$-free graph of minimum degree at least $d$ contains an induced bipartite subgraph of average degree at least $\log d-16t\log\log d$. This follows from our bound $χ_f(G)\le d/(\log d-16t\log\log d)$ for every $d$-degenerate $K_{t,t}$-free graph $G$, which answers a problem of Allen,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.26277
curl -X POST /api/v1/records/arxiv/2611.26277/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.26277/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'