Reducing graph coloring to clique search

MaRDI QIDQ326946zbMATH OpenFDO

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

Publication date 12 October 2016

Published in Asia Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL http://apjm.apacific.org/PDFs/3-1-64-85.pdf

zbMATH Keywords

2-fold coloring3-clique free coloringcliqueclique search algorithm vertex coloringedge coloringgreedy coloring algorithmindependent set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• Reducing hypergraph coloring to clique search
• Decomposing clique search problems into smaller instances based on node and edge colorings
• Clique-relaxed graph coloring
• Exact algorithms to clique-colour graphs
• Complexity of clique coloring and related problems
• Coloring Clique-free Graphs in Linear Expected Time
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• Graph reduction in the construction of minimal clique cover

Cites work

• A fast algorithm for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• An exact algorithm for the maximum clique problem
• Graph Theory and Probability
• Greedy algorithms for triangle free coloring
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 2226810 (Why is no real title available?)
• Monotonic matrices and clique search in graphs
• New methods to color the vertices of a graph
• Sur le coloriage des graphs
• Test case generators and computational results for the maximum clique problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring

Cited in

(9)

• Decomposing clique search problems into smaller instances based on node and edge colorings
• Estimating clique size by coloring the nodes of auxiliary graphs
• Reducing hypergraph coloring to clique search
• Edge coloring of graphs, uses, limitation, complexity
• Coloring the nodes of a directed graph
• scientific article; zbMATH DE number 7407404 (Why is no real title available?)
• The complexity of an exotic edge coloring of graphs
• Clique-relaxed graph coloring
• Clique number estimate based on coloring of the nodes

This page was built for publication: Reducing graph coloring to clique search

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