Sharp quadratic $χ$-binding functions for powers of bipartite graphs
For every natural number $r\geq 2$, we construct $r^{th}$ powers of bipartite graphs whose chromatic number is quadratic in their clique number, showing that the straightforward quadratic upper bound is best possible. We thereby settle an open problem posed by Chakraborty, Chandran, Jacob and Pillai [J. Graph Theory 112(3) (2026), 235-254] by establishing the sharpness of the quadratic bound for squares of bipartite graphs.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27396
curl -X POST /api/v1/records/arxiv/2608.27396/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27396/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'