๐ฎ
๐ฎ
The Ethereal
Borel Vizing's Theorem for Graphs of Subexponential Growth
June 30, 2023 ยท The Ethereal ยท ๐ arXiv.org
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal