1.5.7 Vertex Coloring

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A graph G=(V,E) .

Problem: Color the vertices of V with the minimum number of colors such that for each edge (i,j) \in E , vertices i and j have different colors.

Implementations

  • DIMACS Implementation Challenges (FORTRAN) (rating 7)
  • Mike Trick's Graph Coloring Resources (C) (rating 7)
  • Neural-Networks for Cliques and Coloring (C) (rating 6)
  • Joe Culberson's Graph Coloring Resources (C) (rating 6)
  • Discrete Optimization Methods (Pascal) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Combinatorica (Mathematica) (rating 3)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 3)

    Related Problems

  • Edge Coloring
  • Independent Set
  • Job Scheduling

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .