98-32: Coloring Graphs with Sparse Neighborhoods

DIMACS TR: 98-32

Coloring Graphs with Sparse Neighborhoods

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-32.ps.gz

DIMACS Home Page