1) The assignment of k colors (or any distinct marks) to the vertices of a graph. 2) The assignment of k colors to the edges of a graph.

A coloring is a proper coloring if no two adjacent vertices or edges have the same color.