Premium
A survey on vertex coloring problems
Author(s) -
Malaguti Enrico,
Toth Paolo
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00696.x
Subject(s) - vertex (graph theory) , bounded function , computer science , greedy coloring , graph coloring , heuristic , mathematics , algorithm , mathematical optimization , theoretical computer science , graph , line graph , graph power , mathematical analysis
This paper surveys the most important algorithmic and computational results on the Vertex Coloring Problem (VCP) and its generalizations. The first part of the paper introduces the classical models for the VCP, and discusses how these models can be used and possibly strengthened to derive exact and heuristic algorithms for the problem. Computational results on the best performing algorithms proposed in the literature are reported. The second part of the paper is devoted to some generalizations of the problem, which are obtained by considering additional constraints [ Bandwidth (Multi) Coloring Problem, Bounded Vertex Coloring Problem ] or an objective function with a special structure ( Weighted Vertex Coloring Problem ). The extension of the models for the classical VCP to the considered problems and the best performing algorithms from the literature, as well as the corresponding computational results, are reported.