Local independent sets and colourings of triangle-free graphs
This AI-assisted draft constructs, for every sufficiently large $D$, a local rule of radius $O((\ln D)^2)$ that produces, on any triangle-free graph $G$ of maximum degree at most $D$, a random independent set that includes each vertex with probability at least $(1-o_D(1))\ln D/D$. Further properties of the rule yield, for every fixed $\varepsilon>0$ and all sufficiently large $D$, a randomised LOCAL algorithm that colours any such finite graph $G$ with at most $(1+\varepsilon)D/\ln D$ colours, with high probability, in $O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)}$ communication rounds.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00677
curl -X POST /api/v1/records/hexagon/2610.00677/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00677/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'