An asymptotically tight bound on the adaptable chromatic number
The adaptable chromatic number of a multigraph G, denoted ?a(G), is the smallest integer k such that every edge labeling, ?, of G from [k] = {1, 2, , k} permits a vertex coloring, ?, of G from [k] such that no edge e = uv has ?(e) = ?(u) = ?(v). Hell and Zhu proved that for any multigraph G with maximum degree ?, the adaptable chromatic number is at most . We strengthen this to the asymptotically best possible bound of for any ?>0.  2012 Wiley Periodicals, Inc. J Graph Theory
coloring probabilistic method adaptable coloring