Optimization Online


A simple branching scheme for Vertex Coloring Problems

Stefano Gualandi (stefano.gualandi***at***unipv.it)
Federico Malucelli (malucell***at***elet.polimi.it)

Abstract: 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.

Keywords: Graph Coloring, Graph Bandwidth-Multicoloring, Branching Scheme

Category 1: Combinatorial Optimization (Graphs and Matroids )

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

Download: [PDF]

Entry Submitted: 11/03/2009
Entry Accepted: 11/03/2009
Entry Last Modified: 09/14/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society