What is the known information in this problem?

What are the decision variables or unknowns in this problem?

What are the constraints on these variables?

Since you know all the maximal cliques, you know all the nodes that are linked to each other. Therefore, if all the nodes in each maximal clique are different colors, in the graph as a whole, every pair of linked nodes will be different colors.

There is no objective in this problem. You will simply search for the first solution.