How can I measure the cost of this algorithm pseudo 3-coloring graph problem using probability algorithm?


Problem: I have a classic 3-coloring graph problem where I have to get at least 2/3 well-colored edges from the total edges. By well-colored I mean that the two vertex of one edge are of different color. I have to use a proabilistic algorithm with polynomial average cost.

¿Solution?: I assign each vertex one of the 3 possible colors randomly. So the probability that one edge is well-colored is 2/3. The cost of assign each vertex a random color is linear if I am not wrong. And since I have 2/3 probability that graph cost is well-colored, the probability of having found a solution is 2/3. So with k being a low natural number of bound attemps and n vertex, algorithm’s cost is $ n^{k}$

Doubts: ¿Is solution reasoning about the time cost okey? ¿Is this solution a sort of Las Vegas algorithm? Thanks in advance.