EUVIMEDEUVIMED entdecken
Crossref

Coloring Locally Sparse Graphs

James Anderson, Abhishek Dhawan, Aiya Kuchukova

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →