Greedy algorithms for triangle free coloring (Q1927697)

It was shown by \textit{I. M. Bomze}, \textit{M. Budinich}, \textit{P. M. Pardalos} and \textit{M. Petillo} [``The maximum clique problem,'' Du, Ding-Zhu (ed.) et al., Handbook of combinatorial optimization. Suppl. Vol. A. Boston: Kluwer Academic Publishers, 1--74 (1999; Zbl 1253.90188)] that in order to design an efficient algorithm for listing all the cliques of maximum size in a graph one must be able to find tight bounds on this size. To this end, the article under review introduces some new colouring schemes using \(s\)-clique free partitioning; that is, the subgraph induced by the set of vertices that are assigned the same colour does not contain a clique of size \(s\). For \(s= 3\) we have a triangle-free colouring. It is shown that it is NP-hard to decide whether a given graph has an \(s\)-clique-free colouring with \(r\) colours for any \(s\geq 2\) and any \(r\geq 3\). Several algorithms are presented for finding triangle-free colourings that use approximately the minimum number of colours, including two greedy algorithms and some satisfiability solvers.