Greedy algorithms for triangle free coloring

MaRDI QIDQ1927697zbMATH OpenFDO

Authors Sándor Szabó, Bogdán Zaválnij

Publication date 2 January 2013

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

\(s\)-clique free coloring\(s\)-clique free setcliqueclique search algorithmgreedy coloringindependent setmaximum cliquesatisfiability solververtex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• Colouring vertices of triangle-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Fast 3-coloring triangle-free planar graphs
• Coloring the Maximal Cliques of Graphs
• A class of three-colorable triangle-free graphs

Cited in

(6)

• Decomposing clique search problems into smaller instances based on node and edge colorings
• Numerical experiments with LP formulations of the maximum clique problem
• Reducing graph coloring to clique search
• scientific article; zbMATH DE number 3906523 (Why is no real title available?)
• scientific article; zbMATH DE number 1870232 (Why is no real title available?)
• scientific article; zbMATH DE number 7407404 (Why is no real title available?)

This page was built for publication: Greedy algorithms for triangle free coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1927697)