摘要：Context: Given a graph and an integer the graph coloring problem consists to use a set of colors to assign to each node of a certain color, so that adjacent vertices have distinct color. Despite the existence of accurate methods capable of determining the staining solution to the problem, it is observed that these techniques have an exponential complexity in some cases. The limitations presented by exact methods when applied to instances of greater complexity motivated the development of several heuristics, able to indicate satisfactory solutions for graphs in general. This paper describes the problem of coloring graphs, presents some of the techniques that can be used in their determination, besides presenting some real problems that can be modeled as a graph and solved based on the result achieved by applying a coloring on.
其他摘要：Context: Given a graph and an integer the graph coloring problem consists to use a set of colors to assign to each node of a certain color, so that adjacent vertices have distinct color. Despite the existence of accurate methods capable of determining the staining solution to the problem, it is observed that these techniques have an exponential complexity in some cases. The limitations presented by exact methods when applied to instances of greater complexity motivated the development of several heuristics, able to indicate satisfactory solutions for graphs in general. This paper describes the problem of coloring graphs, presents some of the techniques that can be used in their determination, besides presenting some real problems that can be modeled as a graph and solved based on the result achieved by applying a coloring on.
关键词：Coloring of graphs;Agorithms;Heuristics;Coloração de Grafos;Algoritmos;Heurísticas
