On Finding Large Cliques when the Chromatic Number is close to the Maximum Degree