Approximation Algorithms for Partially Colorable Graphs

Graph coloring is a fundamental NP-hard problem in the study of algorithms. A graph is said to be “partially -colorable” if the graph induced on a “large” subset of the vertices can be colored using  colors. Partial -colorability is a more robust graph property than -colorability. Our work gave bi-criteria approximation algorithms for partially coloring partially -colorable graphs.

Reference

• Title: Approximation Algorithms for Partially Colorable Graphs
• Authors: Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
• Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019
• Other details can be found here: https://drops.dagstuhl.de/opus/volltexte/2019/11243/