Graph coloring when available colors are less than chromatic number

Solution 1:

Check out the Maximum Satisfiability Problem or MAX-SAT https://en.wikipedia.org/wiki/Maximum_satisfiability_problem