An approximate algorithm for the chromatic number of graphs

DOI10.1016/J.ENDM.2014.08.013zbMATH Open1337.05104OpenAlexW2024831296MaRDI QIDQ283679FDOQ283679

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

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}\)

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)

Cites Work

• Algorithmic graph theory and perfect graphs
• 3-coloring in time
• Graphs, Algorithms, and Optimization
• Title not available (Why is that?)

Cited In (11)

• An approximation chromatic number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximating the chromatic number
• Algorithmic bounds for the chromatic number†
• New algorithm for calculating chromatic index of graphs and its applications
• New Algorithm for Chromatic Number of Graphs and their Applications
• An approximate algorithm for the \( (k,d)\)-coloring problem
• Title not available (Why is that?)
• Three-quarter approximation for the number of unused colors in graph coloring
• Title not available (Why is that?)

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)