Palette sparsification for graphs with sparse neighborhoods

A seminal palette sparsification result of Assadi, Chen, and Khanna states that in every n -vertex graph of maximum degree Δ, sampling Θ ⁡ ( l o g ⁡ 𝑛 ) 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 𝑂 ⁢ ( Δ / l o g ⁡ Δ ) -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 𝐺 = ( 𝑉 , 𝐸 ) is k -locally-sparse if for each vertex 𝑣 ∈ 𝑉 , the subgraph 𝐺 ⁡ [ 𝑁 ⁡ ( 𝑣 ) ] contains at most k edges. A celebrated result of Alon, Krivelevich, and Sudakov shows that such graphs are 𝑂 ⁢ ( Δ / l o g ⁡ ( Δ / √ 𝑘 ) ) -colorable. For any 𝛼 ∈ ( 0 , 1 ) and 𝑘 ≪ Δ 2 ⁢ 𝛼 , let G be a k -locally-sparse graph. For 𝑞 = Θ ⁢ ( Δ / l o g ⁡ ( Δ 𝛼 / √ 𝑘 ) ) , we show that sampling 𝑂 ⁢ ( Δ 𝛼 + √ l o g ⁡ 𝑛 ) colors per vertex is sufficient to obtain a proper q -coloring of G from the sampled colors. Setting 𝑘 = 1 recovers the aforementioned result of Alon and Assadi for triangle-free graphs. We establish this result in the more general setting of correspondence coloring where the structural constraints are placed on the correspondence cover as opposed to on the underlying graph. Such a notion has gathered much interest in recent years. A key element in our proof is a proposition which determines sufficient conditions on the correspondence cover ℋ for G to admit a proper ℋ -coloring. This result improves upon recent work of Anderson, Kuchukova, and the author, and is of independent interest.