Approximability Distance in the Space of H-Colourability Problems

DOI10.1007/978-3-642-03351-3_11zbMATH Open1248.68376OpenAlexW1549776389MaRDI QIDQ3392945

Johan Thapper, Peter Jonsson, Tommy Färnqvist

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_11

zbMATH Keywords

computational complexityoptimisationgraph homomorphismapproximabilitygraph \(H\)-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Theory and Probability
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Bipartite subgraphs
• Homomorphisms from sparse graphs with large girth.
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Cliques in random graphs
• The chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• The chromatic number of random graphs
• Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Approximation Algorithms for Graph Homomorphism Problems
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Edges in graphs with large girth
• Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
• MAX k‐CUT and approximating the chromatic number of random graphs
• How to Round Any CSP
• A note on bipartite subgraphs of triangle-free regular graphs
• Bipartite density of cubic graphs
• Fractional covering by cuts
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• Every 2-CSP allows nontrivial approximation

Cited In (2)

• Title not available (Why is that?)
• Properties of an approximability-related parameter on circular complete graphs

This page was built for publication: Approximability Distance in the Space of H-Colourability Problems

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