An approximate algorithm for the chromatic number of graphs

DOI10.1016/J.ENDM.2014.08.013MaRDI QIDQ283679zbMATH OpenOpenAlexFDO

Authors Guillermo de Ita Luna, J. Raymundo Marcial-Romero, Yolanda Moyao

Publication date 13 May 2016

Full work available at URL https://doi.org/10.1016/j.endm.2014.08.013

zbMATH Keywords

approximation algorithmchromatic numbergraph coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• New approximation algorithms for graph coloring
• Algorithmic bounds for the chromatic number†
• Improving the performance guarantee for approximate graph coloring
• An approximation chromatic number of a graph
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)

Cites work

• scientific article; zbMATH DE number 1748997 (Why is no real title available?)
• 3-coloring in time
• Algorithmic graph theory and perfect graphs
• Graphs, Algorithms, and Optimization

Cited in

(11)

• scientific article; zbMATH DE number 6096704 (Why is no real title available?)
• scientific article; zbMATH DE number 1947053 (Why is no real title available?)
• scientific article; zbMATH DE number 1405798 (Why is no real title available?)
• An approximate algorithm for the \( (k,d)\)-coloring problem
• On the hardness of approximating the chromatic number
• New algorithm for calculating chromatic index of graphs and its applications
• Three-quarter approximation for the number of unused colors in graph coloring
• scientific article; zbMATH DE number 1998817 (Why is no real title available?)
• New Algorithm for Chromatic Number of Graphs and their Applications
• An approximation chromatic number of a graph
• Algorithmic bounds for the chromatic number†

This page was built for publication: An approximate algorithm for the chromatic number of graphs

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