Borel Vizing's Theorem for Graphs of Subexponential Growth
share
We show that every Borel graph G of subexponential growth has a Borel proper edge-coloring with Δ(G) + 1 colors. We deduce this from a stronger result, namely that an n-vertex (finite) graph G of subexponential growth can be properly edge-colored using Δ(G) + 1 colors by an O(log^∗ n)-round deterministic distributed algorithm in the 𝖫𝖮𝖢𝖠𝖫 model, where the implied constants in the O(·) notation are determined by a bound on the growth rate of G.
READ FULL TEXT