Executive Summary : | The conflict-free coloring problem on graphs seeks to assign colors to the vertices of a graph, such that for every vertex, there is a color that is assigned to exactly one vertex in its neighborhood. The smallest number of colors required for such a coloring is called conflict-free chromatic number. The notion of conflict-free coloring was introduced in 2002 by Even, Lotker, Ron and Smorodinsky motivated by the problem of assigning frequencies to communication networks. Originally stated for set systems, the graph formulation was later put forth by Cheilaris, and Pach and Tardos around 2008. This problem has been studied from different perspectives. In this project, we intend to study the following aspects of the problem. The problem has been studied with respect to both closed neighborhood and open neighborhood. * Study the problem on specific classes of graphs. Due to the original motivation of frequency assignment in communication networks, geometric variants of the problem have attracted special interest. For example, if we consider unit square graphs, it is known that five colors are enough to conflict-free color unit square graphs (in the closed neighborhood setting). However, it is not known whether this bound is tight. For several such graph classes, the problem can be investigated from two angles --- one is the complexity of the problem when the input graph is restricted to these classes, and two is the bound for the conflict-free chromatic number for these classes. * Study with respect to parameters. Graphs have different structural parameters like vertex cover number, feedback vertex set number, treewidth etc. For example, for the open neighborhood variant, it is known that for a graph with treewidth t, the conflict-free chromatic number is at most 2t+1. We know of graphs for which the conflict-free chromatic number is at most t+1. It would be interesting to know the tight bound. In previous work, we have shown slightly improved bounds for pathwidth, which is a parameter similar to treewidth. * Another interesting question is algorithmic. The problem is in general NP complete. At this point, it is pertinent to ask if there are subclasses of graphs on which this problem can be efficiently solved? This is another interesting direction of work. |