COLORING

OPTIMIZATION PROBLEM

Given G, find the minimum number of colors to color G. (X(G)?)

DECISION PROBLEM

Given graph G and positive integer k, is

EQUIVALENCE OF OPTIMAIZTION AND DECISION PROBLEMS
CHROMATIC NUMBER OF G

• Edge Coloring