Borel Vizing's Theorem for Graphs of Subexponential Growth

June 30, 2023 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Anton Bernshteyn, Abhishek Dhawan arXiv ID 2307.00095 Category math.CO: Combinatorics Cross-listed cs.DC, math.LO Citations 7 Venue arXiv.org Last Checked 6 months ago
Abstract
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^\ast n)$-round deterministic distributed algorithm in the $\mathsf{LOCAL}$ model, where the implied constants in the $O(\cdot)$ notation are determined by a bound on the growth rate of $G$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago