It depends a lot what you exactly you mean by "constructive". You can replace randomization by a greedy algorithm, or by a deterministic strategy similar to the one developed by Beck for combinatorial games (Combinatorial games: Tic-Tac-Toe theory, Encyclopedia of Mathematics and its Applications, Cambridge university press). This results in deterministic algorithms with running times similar to the naive test procedure, so if you want to have one graph colouring of a fixed graph avoiding certain monochromatic substructures, randomization does not help too much.

However, you do not get any structural understanding of the construction, nor do you get the existence for all $n$.