Give each vertex the smallest color its neighbours do not have. The order you go in decides how many colors you need.
This interactive visualization needs JavaScript.