Define the "Graph Coloring Problem".

Assign a color to a vertex of a graph such that no adjacent vertices of the graph have the same color

Assign colors to the vertices in such a way that half of the vertices have the same color while the other half of the vertices have a different color

Assign colors to the vertices of a graph in such a way that all vertices at the same level have the same color

Assign colors to the edges of a graph such that no two edges from a vertex have the same color