We present a branching scheme for some Vertex Coloring Problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as the graph multicoloring, where each vertex requires a multiplicity of colors, the graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, that generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the new branching scheme effectiveness.

## Citation

S. Gualandi, F. Malucelli. A simple branching scheme for Vertex Coloring Problems. Discrete Applied Mathematics, 160(1-2):192-196, 2012. DOI: 10.1016/j.dam.2011.10.012