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

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

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

• 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
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• 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 colouring problems on dense graphs
• The Complexity of Near-Optimal Graph Coloring

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)