Graph Coloring Problem (GCP)
[Chinese version]

Let G=(V, E) be an undirected graph, where V is a set of vertices and E is a set of edges, the graph coloring problem (GCP) is to partition V into K color classes, where each is a subset of V labeled with same color. For a proper coloring, each color class forms an independent set, which has no adjacent vertices. GCP is one of the most notorious models in graph theory. It also has various applications, such as timetabling, register allocation, etc.

Related Papers

  • Xiao-Feng Xie, Jiming Liu. Graph coloring by multiagent fusion search. Journal of Combinatorial Optimization, 2009, 18(2): 99-123. [DOI]
  • Software Download
    name type* description
    MAOS_GCP SRC JAVA, Multiagent Optimizer for solving GCP in DIMACS format
    *abbreviations: SRC=source code; BIN=binary code
    Return to homepage

    Maintained by AdaptiveBox StUdIo, under a Creative Commons Attribution 3.0 License.