Oleg Pikhurko

math.CO — Combinatorics

Local independent sets and colourings of triangle-free graphs

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko

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. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.