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