Approximability Distance in the Space of H-Colourability Problems
DOI10.1007/978-3-642-03351-3_11zbMATH Open1248.68376OpenAlexW1549776389MaRDI QIDQ3392945FDOQ3392945
Authors: Tommy Färnqvist, Peter Jonsson, Johan Thapper 
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
Recommendations
- Approximation Algorithms for Graph Homomorphism Problems
- An approximability-related parameter on graphs -- properties and applications
- Properties of an approximability-related parameter on circular complete graphs
- Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Improved inapproximability results for maximum \(k\)-colorable subgraph
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?)
- 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.
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
- Every 2-CSP allows nontrivial approximation
Cited In (4)
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)
