Abstract: We discuss the relationship between greedy colouringand Grundy number, and we prove that finding Grundy number of a graph is an NP-hard problem.We also introduce the concept of randomly colourable graphs, implore some properties of them and prove that recognizing a graph to be randomly colourable is an NP-hard problem.

Key words: greedy colouring, Grundy number, randomly colourable graph