Research Projects

The aim of this project is to study the computational complexity of some combinatorial optimization problems associated with some generalizations of graph coloring problem. For example, given a graph $G$, in Minimum $(k,l)$-Partization it is required to find a vertex set $S \subseteq V$ of minimum size such that $G[V\setminus S]$ is a $(k, l)$-graph. In literature, researchers have studied this problem in terms of exact exponential algorithms. In this project, we aim to study designing polynomial time approximation algorithms and proving lower bound results on the approximation factor. It is important to note that such kinds of results are interesting as long as $k$ and $l$ are at most 2. We also plan to investigate the complexity of the Minimum $H$-Coloring-Partization for various graphs $H$ and Minimum $k$-Choosable-Partization. Apart from this kind of minimum partization problem, we aim to find an interesting subclass of graphs for which there are polynomial time recognization algorithms for larger values of $k$ and $l$.