Greedy algorithms for triangle free coloring
type: Item
instance of: scholarly article
title: Greedy algorithms for triangle free coloring
zbMATH Open document ID: 1262.05063
published in: AKCE International Journal of Graphs and Combinatorics
publication date: 2013-01-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6120581
zbMATH Keywords: clique
zbMATH Keywords: maximum clique
zbMATH Keywords: independent set
zbMATH Keywords: vertex coloring
zbMATH Keywords: \(s\)-clique free set
zbMATH Keywords: \(s\)-clique free coloring
zbMATH Keywords: clique search algorithm
zbMATH Keywords: satisfiability solver
zbMATH Keywords: greedy coloring
author: Sándor Szabó
author: Bogdán Zaválnij
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6120581