People in social networks usually form cliques – groups in which every two persons interact with each other. The problem of finding the largest clique in a network is called the maximum clique problem. This problem can be exactly solved with a branch-and-bound algorithm in which the vertex coloring problem is used to compute upper bounds. In this talk we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value δ. The obtained increase in performance reaches 70% on benchmark instances.