Improved Inapproximability Results for Maximum k-Colorable Subgraph
DOI10.1007/978-3-642-03685-9_13zbMATH Open1255.68072OpenAlexW2122906648MaRDI QIDQ3638876FDOQ3638876
Authors: Ali Kemal Sinop, Venkatesan Guruswami 
Publication date: 28 October 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_13
Recommendations
- Improved inapproximability results for maximum \(k\)-colorable subgraph
- The Maximum k-Colorable Subgraph Problem and Related Problems
- Improved approximation algorithms for the max-edge coloring problem
- Approximating the maximum 2- and 3-edge-colorable subgraph problems
- Improved approximation algorithms for the max edge-coloring problem
- Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)
- Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
- Approximating the maximum 3-edge-colorable subgraph problem
- Improved approximation for maximum edge colouring problem
- The maximum k-colorable subgraph problem for chordal graphs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cited In (7)
- Colouring graphs when the number of colours is nearly the maximum degree
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Improved hardness of approximating chromatic number
- Improved inapproximability results for maximum \(k\)-colorable subgraph
- An approximability-related parameter on graphs -- properties and applications
- Approximability Distance in the Space of H-Colourability Problems
- Improved approximations for the max \(k\)-colored clustering problem
This page was built for publication: Improved Inapproximability Results for Maximum k-Colorable Subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638876)
