##
1.5.7 Vertex Coloring

##
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
.