  This paper presents a variable neighborhood search (VNS) algorithm for
solving bandwidth coloring problem (BCP) and bandwidth multicoloring problem
(BMCP). BCP and BMCP are generalizations of the well known vertex coloring
problem and they are of a great interest from both theoretical and practical
points of view. Presented VNS combines a shaking procedure which perturbs the
colors for an increasing number of vertices and a specific variable
neighborhood descent (VND) procedure, based on the specially designed
arrangement of the vertices which are the subject of re-coloring. By this
approach, local search is split in a series of disjoint procedures, enabling
better choice of the vertices which are addressed to re-color. The experiments
show that proposed method is highly competitive with the state-of-the-art
algorithms and improves 2 out of 33 previous best known solutions for BMCP.
