Fixed parameters tractability of graph colouring and related problems.

The field of parameterized complexity is one of the newest approaches in dealing with NP-hard problems. Fixed parameter theory, mainly developed by Rod Downey and Mike Fellows, tries to identify which of NP-hard problems have algorithms with run-ning time OU (Orli, where f is some arbitrary (exponential or worse) function of a parameter k, and c is a constant independent of k and n, where n is the input size. Such an algorithm is of practical importance for small values of the parameter k. Some NP-hard problems have been shown to have extremely good fixed parameter algorithms, allowing them to be solved efficiently for quite high values of the parameter. One of the best examples of such problems is the NP-hard vertex cover problem, where the best known running time is 0(1.273k + kii) making it useful for k as large as 400. Parameterized complexity has applications in various fields such as computational biology, artificial intelligence and database theory. In this thesis, we study combinatorial hard problems on graphs from the point of view of parameterized complexity. Problems considered are: graph colouring, independent sets, clique covering and clique covering. The study has found new results on these problems. Some of these new results presented in this thesis have been included in [50], [100] and [99]; the first and the second of these papers have been published already, while the third paper has been accepted for publication.