Estimating clique size by coloring the nodes of auxiliary graphs

Abstract

It is a common practice to find upper bound for clique number via legal coloring of the nodes of the graph. We will point out that with a little extra work we may lower this bound. Applying this procedure to a suitably constructed auxiliary graph one may further improve the clique size estimate of the original graph.

Keywords

• clique number
• chromatic number
• maximum clique legal coloring of the nodes
• greedy coloring
• 05c15
• 05b45
• 52c22