A clique size estimate based on coloring the nodes
of certain subgraphs

Abstract. Many of the maximum clique search algorithms used in practice employ a routine to establish upper estimate of the clique size of a given graph. The upper estimates are typically based on legally coloring the nodes in some greedy manner. Motivated by these facts we propose a upper estimate for the clique number. Using any greedy coloring procedure the nodes of many subgraphs are colored legally and then these partial results are combined together to a clique size upper estimate.