A proper colouring of a graph is a function that assigns a colour to each vertex with the restriction that adjacent vertices are assigned with distinct colours. Proper colourings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper colouring of a graph with the minimum number of colours is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colourings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number of a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and P4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least |V(G)| - k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameters of a graph.
