1.5.8 Edge Coloring

Problem Input | Problem Output

INPUT                    OUTPUT

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

Problem: What is the smallest set of colors needed to color the edges of E such that no two edges with the same color share a vertex in common?


  • Stony Brook Project Implementations (C++) (rating 6)
  • Combinatorica (Mathematica) (rating 4)
  • Joe Culberson's Graph Coloring Resources (C) (rating 4)
  • Mike Trick's Graph Coloring Resources (C) (rating 4)

    Related Problems

  • Job Scheduling
  • Vertex Coloring

    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 .