Improved Inapproximability Results for Maximum k-Colorable Subgraph

DOI10.1007/978-3-642-03685-9_13MaRDI QIDQ3638876zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

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

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)