Premium
An asymptotically tight bound on the adaptable chromatic number
Author(s) -
Molloy Michael,
Thron Giovanna
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20649
Subject(s) - multigraph , combinatorics , mathematics , chromatic scale , vertex (graph theory) , integer (computer science) , graph , upper and lower bounds , edge coloring , critical graph , discrete mathematics , enhanced data rates for gsm evolution , computer science , graph power , line graph , mathematical analysis , telecommunications , programming language
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