I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen here on slide 60.
The problem summary is given a graph G and variable k, are there k disjoint triangles in the graph. There are two methods, I want to focus on one of them. (Method 1)
First I randomly color the graph in 3k colors and then go over each permutation of colors and check whether there are k triangles with distinct colors.
What I fail to understand is what the time complexity of such examination (going over all the possible permutations) and how exactly can it be done?