Graph colouring problems are hugely popular as models of abstraction to represent relationships between entities. Vertex colouring problem is among the most well-studied variants of colouring problems in simple graphs as well as hypergraphs. The relevance of vertex colouring is not just as a tool of prototyping but also as a model problem from a computational complexity perspective. In this thesis, we study a vertex colouring problem in hypergraphs known as the conflict-free colouring problem. Motivated by the frequency assignment problem in cellular networks, the conflict-free colouring problem was first studied by Even, Lotker, Ron and Smorodinsky on hypergraphs induced by geometric regions. The literature on conflict-free colouring is rich with results on bounds for optimum number of colours in general as well as specific hypergraphs, obtained through algorithmic, probabilistic and/or combinatorial techniques. We study the conflict-free colouring problem in general hypergraphs in terms of well-studied parameters in two sets of associated simple graphs that we introduce - co-occurrence graphs and conflict graphs. The outcome of this study is a new framework for the conflict-free colouring problem. We solve the complexity status of the conflict-free colouring problem in interval hypergraphs using this framework by devising an algorithm to solve the problem optimally in P-time. Apart from the machinery provided by the framework, important structural properties of co-occurrence graphs and conflict graphs of interval hypergraphs, have been instrumental in obtaining an efficient solution for interval hypergraphs. We show that the co-occurrence graphs and conflict graphs of interval hypergraphs are perfect graphs. The class of perfect graphs is popular as one of the most interesting classes of simple graphs having P-time algorithms for vertex colouring, maximum independent set and maximum clique problems. These P-time algorithms are crucial to the efficiency of our solution. In addition to a framework for conflict-free colouring, our characterizations have also provided instruments for proving hardness results in other models of computing.

Hitting set problems are said to be the foundation stones for the entire field of approximation algorithms. Many combinatorial problems can be formulated as a hitting set problem or its dual -- set cover problem. With this fact in perspective, it is not surprising that the conflict-free colouring problem is closely related to a variant of the classical minimum hitting set problem. We refer to this variant as the minimum membership hitting set problem. We present a new upper bound for the conflict-free colouring number in interval hypergraphs in terms of the value of an optimal solution to the MMHS instance of the input hypergraph. Even though our P-time exact algorithm for the conflict-free colouring problem in interval hypergraphs subsumes this new bound, we believe that this bound could serve as a precedent for obtaining better bounds or even exact algorithms in other special classes of hypergraphs having structural similarity to interval hypergraphs. In addition to the relationship with conflict-free colouring, we study the minimum membership hitting set problem on hypergraphs induced by axis parallel objects in the 2-dimensional plane that include segments, rays and lines. We present algorithms or hardness results for these hypergraphs and show that our results are in line with known results on Dominating set and Set cover problems in similar sets of hypergraphs.