Greedy algorithms for triangle free coloring (Q1927697)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Greedy algorithms for triangle free coloring |
scientific article |
Statements
Greedy algorithms for triangle free coloring (English)
0 references
2 January 2013
0 references
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.
0 references
clique
0 references
maximum clique
0 references
independent set
0 references
vertex coloring
0 references
\(s\)-clique free set
0 references
\(s\)-clique free coloring
0 references
clique search algorithm
0 references
satisfiability solver
0 references
greedy coloring
0 references