A clique size estimate based on coloring the nodes of certain subgraphs
Sándor Szabó · Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatorica · 2018
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.