Coloring Graphs with Sparse Neighborhoods

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

77 Scopus citations


It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d2/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.

Original languageEnglish (US)
Pages (from-to)73-82
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Issue number1
StatePublished - Sep 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Coloring Graphs with Sparse Neighborhoods'. Together they form a unique fingerprint.

Cite this