Borel Vizing’s theorem for graphs of subexponential growth
Copyright policy )Borel Vizing’s theorem for graphs of subexponential growth
We show that every Borel graph G G of subexponential growth has a Borel proper edge-coloring with Δ ( G ) + 1 \Delta (G) + 1 colors. We deduce this from a stronger result, namely that an n n -vertex (finite) graph G G of subexponential growth can be properly edge-colored using Δ ( G ) + 1 \Delta (G) + 1 colors by an O ( log ∗ n ) O(\log ^\ast n) -round deterministic distributed algorithm in the LOCAL model, where the implied constants in the O ( ⋅ ) O(\cdot ) notation are determined by a bound on the growth rate of G G .
- GEORGIA TECH RESEARCH CORPORATION United States
Borel graph, FOS: Computer and information sciences, Borel chromatic number, Classes of sets (Borel fields, \(\sigma\)-rings, etc.), measurable sets, Suslin sets, analytic sets, Mathematics - Logic, distributed computing, Coloring of graphs and hypergraphs, Infinite graphs, Computer Science - Distributed, Parallel, and Cluster Computing, FOS: Mathematics, Distributed algorithms, Mathematics - Combinatorics, Combinatorics (math.CO), Distributed, Parallel, and Cluster Computing (cs.DC), Logic (math.LO), Descriptive set theory, LOCAL algorithm
Borel graph, FOS: Computer and information sciences, Borel chromatic number, Classes of sets (Borel fields, \(\sigma\)-rings, etc.), measurable sets, Suslin sets, analytic sets, Mathematics - Logic, distributed computing, Coloring of graphs and hypergraphs, Infinite graphs, Computer Science - Distributed, Parallel, and Cluster Computing, FOS: Mathematics, Distributed algorithms, Mathematics - Combinatorics, Combinatorics (math.CO), Distributed, Parallel, and Cluster Computing (cs.DC), Logic (math.LO), Descriptive set theory, LOCAL algorithm
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!