A simple branching scheme for vertex coloring problems

DOI10.1016/j.dam.2011.10.012zbMath1237.05075OpenAlexW1999377519MaRDI QIDQ765355

Federico Malucelli, Stefano Gualandi

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.012

zbMATH Keywords

graph coloringvertex coloringextension operatorbranching schemegraph bandwidth coloringgraph bandwidth multicoloringgraph extension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Total coloring and total matching: polyhedra and facets ⋮ Exploring the role of graph spectra in graph coloring algorithm performance ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ Constraint programming-based column generation ⋮ Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

Uses Software

• CALMA

Cites Work

• Unnamed Item
• A column generation and branch-and-cut algorithm for the channel assignment problem
• Frequency assignment in mobile radio systems using branch-and-cut techniques
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A survey on vertex coloring problems
• A Branch-And-Price Approach for Graph Multi-Coloring
• Determining the Chromatic Number of a Graph
• A Column Generation Approach for Graph Coloring
• An Algorithm for Determining the Chromatic Number of a Graph
• Models and solution techniques for frequency assignment problems

This page was built for publication: A simple branching scheme for vertex coloring problems