A simple branching scheme for vertex coloring problems

作者：Gualandi Stefano; Malucelli Federico^*

来源：Discrete Applied Mathematics, 2012, 160(1-2): 192-196.

DOI：10.1016/j.dam.2011.10.012

• Graph coloring
• Graph bandwidth multicoloring
• Branching scheme

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 graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.

• 出版日期2012-1