An approximation algorithm for 3-Colourability

DOI10.1007/3-540-60618-1_72MaRDI QIDQ6122218zbMATH OpenFDO

Authors Ingo Schiermeyer

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60618-1_72

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• New approximation algorithms for graph coloring
• Polynomial approximation and graph-coloring
• Deciding 3-colourability in less than O(1.415n) steps
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• On the hardness of approximating the chromatic number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• A note on the complexity of the chromatic number problem
• Algorithms for maximum independent sets
• An algorithm for the chromatic number of a graph
• Finding a Maximum Independent Set
• Graph theory with applications
• New approximation algorithms for graph coloring
• On cliques in graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Solving satisfiability in less than \(2^ n\) steps
• The Complexity of Near-Optimal Graph Coloring
• The complexity of colouring problems on dense graphs

This page was built for publication: An approximation algorithm for 3-Colourability

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