  


A simple branching scheme for Vertex Coloring Problems
Stefano Gualandi (stefano.gualandiunipv.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 BandwidthMulticoloring, 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(12):192196, 2012. DOI: 10.1016/j.dam.2011.10.012 Download: [PDF] Entry Submitted: 11/03/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  