The inputs are a graph G and an integer k.  The goal is to color all the vertices with at most k colors in such a way that no 2 adjacent vertices have the same color.  It's possible that there may be no such coloring.

Here's a video: https://youtu.be/3VeQhNF5-rE