{"id":"hexagon/2610.00677","pdf":"https://hexagonmath.org/pdf/2610.00677v1","url":"https://hexagonmath.org/abs/2610.00677v1","tags":["math.LO","cs.DM","cs.DS","msc:05C15","Chromatic number","LOCAL algorithm","descriptive combinatorics","independent set","triangle-free graphs"],"score":0,"title":"Local independent sets and colourings of triangle-free graphs","domain":"math.CO","origin":"ai-generated","source":"hexagon","authors":["Matthew Bowen","András Máthé","Oleg Pikhurko"],"reviews":0,"subject":"math.CO","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"ai_models":["ChatGPT"],"discussed":0,"published":"2026-10-31","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","formalized":false,"human_understanding":"some"}