2024/03/05 by Abhishek Dhawan, Dhawan, Abhishek · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2403.03054
openalex publication_date 2024/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) is (k, r)-locally-sparse if for each vertex v ∈ V(G), the subgraph induced by its neighborhood contains at most k cliques of size r. For r ≥ 3 and ε∈ [0, 1], we show that an n-vertex (Δεr, r)-locally-sparse graph G of maximum degree Δ satisfies α(G) = (1-o(1))\dfracnηΔ and χ(G) = O(ηΔ), where η:=ε+ \dfracrloglog Δlog Δ. For ε not too large, the hidden constant in the O(⋅) can be taken to be 1+o(1). Setting ε= 0, we recover classical results on Kr+1-free graphs due to Shearer and Johansson, which were more recently improved by Davies, Kang, Pirot, and Sereni. We prove a stronger result on the independence number in terms of the occupancy fraction in the hard-core model, and establish a local version of the coloring result in the more general setting of correspondence coloring.