Borel Vizing's theorem for graphs of subexponential growth

DOI10.1090/proc/17048MaRDI QIDQ6654016

Abhishek Dhawan, Anton Bernshteyn

Publication date: 18 December 2024

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

distributed computingBorel graphBorel chromatic numberLOCAL algorithm

Mathematics Subject Classification ID

Descriptive set theory (03E15) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Infinite graphs (05C63)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A constructive proof of Vizing's theorem
• Borel chromatic numbers
• Measurable versions of Vizing's theorem
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
• A determinacy approach to Borel combinatorics
• Graph Theory
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Unfriendly colorings of graphs with finite average degree
• Orienting Borel graphs
• Some simple distributed algorithms for sparse networks
• Deterministic distributed edge-coloring with fewer colors
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Definable Kőnig theorems
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• The power of multi-step Vizing chains
• Improved distributed algorithms for the Lovász local lemma and edge coloring
• On an estimate of the chromatic class of a \(p\)-graph
• Borel edge colorings for finite-dimensional groups

This page was built for publication: Borel Vizing's theorem for graphs of subexponential growth