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