Research Projects

The project deals with an algorithmic study of the coupon coloring problem in graphs. This is a variant of the vertex coloring problem in graphs which was introduced recently in 2015. Like many other coloring problems, the coupon coloring problem has also found applications in various fields including multi-robotic networks, coding theory etc. This problem is also equivalent to the total domatic number problem in graph theory, which is a problem in the area of graph domination. Thus the coupon coloring problem lies in the intersection of two important subareas of graph theory called graph coloring and graph domination. The problem is known to be NP-complete. Apart from that not many algorithmic results are known. We intend to fill this gap by studying various algorithmic aspects of this problem including the following. 1. The complexity of the coupon coloring problem restricted to special graph classes. 2. The parameterised complexity of the coupon coloring problem under various parameterisations. 3. Efficient approximation algorithms for the coupon coloring problem. We believe there is further scope in the study where the above mentioned techniques can be combined to get efficient algorithms.