Reducing graph coloring to clique search (Q326946)

Summary: Coloring the nodes of a graph is a widely used technique to speed up practical clique search algorithms. This motivates our interest in various graph coloring schemes. Because of computational costs mainly simple greedy graph coloring procedures are considered. In this paper we will show that certain graph coloring schemes can be reduced to finding cliques in an appropriately constructed auxiliary graph. Once again because of computational costs involved one has to resort on not exhaustive clique search procedures. These lead to new greedy graph coloring algorithms which can be used as preconditioning tools before embarking on large scale clique searches.