Bounds for the Independence and Chromatic Numbers of Locally Sparse Graphs
Abhishek Dhawan · Annals of Combinatorics · 2025
Abstract In this note, we consider a more general version of local sparsity introduced recently by Anderson, Kuchukova, and the author. In particular, we say a graph $$G = (V, E)$$ G = ( V , E ) is ( k , r )-locally sparse if, for each vertex $$v \in V(G)$$ v ∈ V ( G ) , the subgraph induced by its neighborhood contains at most k cliques of size r . For $$r \geqslant 3$$ r ⩾ 3 and $$\varepsilon \in [0, 1]$$ ε ∈ [ 0 , 1 ] , we show that an n -vertex $$(\Delta ^{\varepsilon r}, r)$$ ( Δ ε r , r ) -locally sparse graph G of maximum degree $$\Delta $$ Δ satisfies $$\alpha (G) \geqslant (1-o(1))\dfrac{n}{\eta \Delta }$$ α ( G ) ⩾ ( 1 - o ( 1 ) ) n η Δ and $$\chi (G) \leqslant \Theta \left( \eta \Delta \right) $$ χ ( G ) ⩽ Θ η Δ , where $$\eta :==\varepsilon + \dfrac{r\log \log \Delta }{\log \Delta }$$ η : = = ε + r log log Δ log Δ . For $$\varepsilon $$ ε not too large, the hidden constant in the