Metaheuristics for robust graph coloring

Fan Wang, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)


This paper studies a robust graph coloring problem, which is a variant of the classical graph coloring problem, where penalties are charged for non-adjacent vertices that are assigned the same color. The problem can be formulated as an unconstrained quadratic programming problem, and has many applications in industry. Since the problem is known to be strongly NP-complete, we develop a number of metaheuristics for it, which are based on various encoding schemes, neighborhood structures, and search algorithms. Extensive experiments suggest that our metaheuristics with a partition based encoding scheme and an improvement graph based neighborhood outperform other methods tested in our study.
Original languageEnglish
Pages (from-to)529-548
Number of pages20
JournalJournal of Heuristics
Issue number4
Publication statusPublished - 1 Aug 2013


  • Metaheuristics
  • Robust graph coloring
  • Unconstrained quadratic programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this