2024/08/15 by Abhishek Dhawan, Dhawan, Abhishek · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2408.08256
openalex publication_date 2024/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A seminal palette sparsification result of Assadi, Chen, and Khanna states that in every n-vertex graph of maximum degree Δ, sampling Θ(log n) colors per vertex from \1, …, Δ+1\ almost certainly allows for a proper coloring from the sampled colors. Alon and Assadi extended this work proving a similar result for O(Δ/log Δ)-coloring triangle-free graphs. Apart from being interesting results from a combinatorial standpoint, their results have various applications to the design of graph coloring algorithms in different models of computation. In this work, we focus on locally sparse graphs, i.e., graphs with sparse neighborhoods. We say a graph G = (V, E) is k-locally-sparse if for each vertex v ∈ V, the subgraph G[N(v)] contains at most k edges. A celebrated result of Alon, Krivelevich, and Sudakov shows that such graphs are O(Δ/log (Δ/√(k)))-colorable. For any α∈ (0, 1) and k ≪ Δ2α, let G be a k-locally-sparse graph. For q = Θ(Δ/log (Δα/√(k))), we show that sampling O(Δα+ √(log n)) colors per vertex is sufficient to obtain a proper q-coloring of G from the sampled colors. Setting k = 1 recovers the aforementioned result of Alon and Assadi for triangle-free graphs. A key element in our proof is a proposition regarding correspondence coloring in the so-called color-degree setting, which improves upon recent work of Anderson, Kuchukova, and the author and is of independent interest.