An asymptotically tight bound on the adaptable chromatic number
Michael S. O. Molloy, Giovanna Thron · Journal of Graph Theory · 2012
Abstract 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