Edge Coloring

VIZING'S THEOREM
Chromatic index of a graph G is either

CLIQUE OPTIMIZATION
Given a graph, find the size of the maximum clique in G.

CLIQUE DECISION
Given G and integer k, does G have a k-clique?

CLIQUE SEARCH
Given G, find a maximum clique of G.

KURATOWSKI'S THEOREM
A graph is planar iff it is not homomorphically reducible to either or

SAT (SATISFIABILITY)

Satisfying Truth Assignment

Variables:

Literals:

Clauses:

SAT: Given n variables and m clauses over these variables, is there a satisfying truth assignment?

3SAT: All clauses have exactly 3 literals.

2SAT: Can be solved in polynomial time.