Graph Coloring and its variants

Abstract

A partition of the vertex set of a graph into independent sets is called a coloring of the graph. The graph coloring problem is, given a graph, to find a coloring with a minimum number of sets in the partition. In this thesis, we study the graph coloring problem and some of its variants, namely star coloring, CD-coloring, and strong subcoloring, from structural as well as algorithmic points of view. The graph coloring problem and its variants arise as natural models of several important optimization problems dealing with issues like scheduling, resource allocation, and etc. in industrial and scientific applications [6; 11; 15; 19; 20; 33; 34; 45].