Coloring

graphs with sparse neighborhoods

Coloring graphs with sparse neighborhoods

Noga Alon∗Michael Krivelevich†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

d2/f is at most O(d/log f).This is tight(up to a constant factor)for all admissible values of d

and f.

1Introduction

The chromatic numberχ(G)of a graph G is the minimum number of colors required to color all

its vertices so that adjacent vertices get distinct colors.It is easy and well known that if d is the

maximum degree of G thenχ(G)≤d+1.This upper bound can be improved if the graph has

sparse neighborhoods,namely,if no subgraph on the set of all neighbors of a vertex spans too many

edges.Thefirst instance of a result of this type is Brooks’Theorem[5],which asserts that if no

neighborhood contains d2 edges(that is,if G contains no copy of the complete graph on d+1 vertices),thenχ(G)≤d.Molloy and Reed[13]proved that for every >0there is someδ>0such

that if no neighborhood contains more than(1− ) d2 edges,thenχ(G)≤(1−δ)(d+1).Johansson [7]proved that if each neighborhood contains no edges at all(that is,if G is triangle-free),then χ(G)≤O(d/log d).Related results for independence numbers of graphs with sparse neighborhoods appeared earlier in[1].Our main result in the present note is the following.

Theorem1.1There exists an absolute positive constant c such that the following holds.Let G=

(V,E)be a graph on n vertices with maximum degree d in which the neighborhood N(v)of any vertex

v∈V spans at most d2/f edges.Then the chromatic number of G is at most c d

.

log f ∗Department of Mathematics,Raymond and Beverly Sackler Faculty of Exact Sciences,Tel Aviv University,Tel Aviv,Israel and Institute for Advanced Study,Princeton,NJ08540.Email:noga@math.tau.ac.il.Research supported in part by a USA Israeli BSF grant,by a grant from the Israel Science Foundation and by a State of New Jersey grant.

†School of Mathematics,Institute for Advanced Study,Princeton,NJ08540.Email:mkrivel@math.ias.edu.Re-

search supported by an IAS/DIMACS Postdoctoral Fellowship.

‡Department of Mathematics,Raymond and Beverly Sackler Faculty of Exact Sciences,Tel Aviv University,Tel

Aviv,Israel.Email:sudakov@math.tau.ac.il.Part of this research was done during a visit at the IAS,Princeton,NJ. Mathematics Subject Classification(1991):05C15,05C35.

Running head:Coloring sparse graphs.

1

第1页下一页