Highly colored vertices in greedy coloring imply existence of subtrees

Question

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.

Answer 1

Let us prove the following claim by induction.

Let $T$ be a colored rooted tree in which each color appears at most once, and the colors of the children of a node are smaller than the color of the node.

Let $G$ be a greedily colored graph, and let $v$ be a vertex whose color is the same as the color of the root of $T$. Then we can embed $T$ into $G$ in such a way that the root gets mapped to $v$ and the colors of all nodes match.

If $T$ consists of a single node, this is clear. Otherwise, let $T_1,\ldots,T_m$ be the subtrees rooted at the children of the root of $T$. Since the colors of the roots of $T_1,\ldots,T_m$ are distinct and smaller than the color of the root of $T$, the node $v$ must have distinct neighbors $v_1,\ldots,v_m$ whose colors match the colors of the roots of $T_1,\ldots,T_m$. Inductively, we can embed $T_1,\ldots,T_m$ into $G$. Since all colors in $T$ are distinct, the embeddings are disjoint, and so can be put together to construct the desired embedding of $T$.

To derive your claim from this one, you need to show that every tree of size $k$ can be colored according to the prescriptions of this claim. You can use BFS to accomplish that.