I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. (It is easy to see that this might not be the optimal coloring possible)
So after the coloring, we see that a vertex has color $k$ which is the highest assigned color in the graph (other vertices might have color $k$ but no vertex has color more than $k$). I would like to say that given any tree on $k$ vertices I can find that tree as a sub-graph of $G$.
My ideas : I observed that the $k$ vertex tree can be found in the graph with one vertex being the one colored $k$ (as one might expect). Moreover I think that if someone mentions any $k$ vertex tree and any node, $v$, in that tree we can find the tree in $G$ with the vertex colored $k$ acting as the node $v$. This is what I tried to induct on but couldn't succeed.