Coloring Graphs with Dense Neighborhoods
Landon Rabern · Journal of Graph Theory · 2013
It is shown that any graph with maximum degree Δ in which the average degree of the induced subgraph on the set of all neighbors of each vertex exceeds is either -colorable or contains a clique on more than vertices. In the case we improve the bound on the average degree to and the bound on the clique number to . As corollaries, we show that every graph satisfies and every graph satisfies .