An approximation algorithm for 3-Colourability

DOI10.1007/3-540-60618-1_72MaRDI QIDQ6122218

Ingo Schiermeyer

Publication date: 28 February 2024

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of colouring problems on dense graphs
• Solving satisfiability in less than \(2^ n\) steps
• On the ratio of optimal integral and fractional covers
• A note on the complexity of the chromatic number problem
• Algorithms for maximum independent sets
• The Complexity of Near-Optimal Graph Coloring
• On the Complexity of Timetable and Multicommodity Flow Problems
• Finding a Maximum Independent Set
• New approximation algorithms for graph coloring
• On the hardness of approximating minimization problems
• An algorithm for the chromatic number of a graph
• On cliques in graphs

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