Authors: Noga Alon, Michael Krivelevich and Benny Sudakov
ABSTRACT
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 d^2/f is at most O( d/ \log f).
This is tight (up to a constant factor) for all admissible values of d and f.
DIMACS Home Page