Coloring Locally Sparse Graphs
The Electronic Journal of Combinatorics · 13.02.2026 · 33 (1)
DOI: 10.37236/13620 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 13.02.2026. Verfasst von James Anderson und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
A graph $G$ is $k$-locally sparse if for each vertex $v \in V(G)$, the subgraph induced by its neighborhood contains at most $k$ edges. Alon, Krivelevich, and Sudakov showed that for $f > 0$ if a graph $G$ of maximum degree $\Delta$ is $\Delta^2/f$-locally-sparse, then $\chi(G) = O\left(\Delta/\log f\right)$. We introduce a more general notion of local sparsity by defining graphs $G$ to be $(k, F)$-locally-sparse for some graph $F$ if for each vertex $v \in V(G)$ the subgraph induced by the neighborhood of $v$ contains at most $k$ copies of $F$. Employing the Rödl nibble method, we prove the following generalization of the above result: for every bipartite graph $F$, if $G$ is $(k, F)$-locally-sparse, then $\chi(G) = O\left( \Delta /\log\left(\Delta k^{-1/|V(F)|}\right)\right)$. This improves upon results of Davies, Kang, Pirot, and Sereni who consider the case when $F$ is a path. Our results also recover the best known bound on $\chi(G)$ when $G$ is $K_{1, t, t}$-free for $t \geq 4$, and hold for list and correspondence coloring in the more general so-called "color-degree" setting.
Zitieren
APA
Anderson, J., Dhawan, A., & Kuchukova, A. (2026). Coloring Locally Sparse Graphs. The Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/13620
Vancouver
Anderson J, Dhawan A, Kuchukova A. Coloring Locally Sparse Graphs. The Electronic Journal of Combinatorics. 2026;33(1). doi:10.37236/13620
BibTeX
@article{Anderson2026,
author = {Anderson, James and Dhawan, Abhishek and Kuchukova, Aiya},
title = {Coloring Locally Sparse Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {1},
doi = {10.37236/13620}
}
EUVIMED