Can a path colored by a greedy algorithm ever have more than 2 colors?

Question

can a path with at least 3 vertices, colored by a greedy coloring algorithm, not have exactly 2 colors?

I believe that the answer is no, but I am not sure if I fully understand greedy coloring. If the answer is yes, can you provide an example?

also would it make a difference if a graph is labeled vs unlabeled? If it does make it difference, can you answer the question for both labeled and unlabeled?

note: only concerned about undirected graphs

Answer 1

Here is one way that a greedy coloring of a path may end up using more than $2$ colors.

Take a path on $4$ vertices:

1 --- 2 --- 3 --- 4

Suppose your greedy algorithm considers them in the order 1, 4, 2, 3.

When looking at vertex 1, there are no already-colored neighbors to watch out for, so the algorithm will give vertex 1 the first available color: say, RED.

RED --- 2 --- 3 --- 4

When looking at vertex 4, there are also no already-colored neighbors to watch out for, so the algorithm will color vertex 4 the same color RED for the same reason.

RED --- 2 --- 3 --- RED

When looking at vertex 2, there is already a RED neighbor, so the greedy algorithm will use the next color on the list: say, BLUE.

RED --- BLUE --- 3 --- RED

Finally, when looking at vertex 3, there are already both RED and BLUE neighbors, so the greedy algorithm will be forced to use a third color: say, GREEN.

RED --- BLUE --- GREEN --- RED.

There we have it.

Finally, note that this is as bad as it gets: with any vertex ordering of any path, each vertex will have at most $2$ previously-colored neighbors, eliminating at most $2$ colors, so you'll never end up with more than $3$ colors.