1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 19 '17 at 6:54
  • $\begingroup$ I don't understand your question. If a vertex is colored $k$ then it has degree at least $k-1$, but I'm not sure you can say anything more. $\endgroup$ – Yuval Filmus Dec 19 '17 at 8:23
  • $\begingroup$ If a vertex is colored $k$ then you can find a star on $k$ vertices, but you cannot find an arbitrary tree on $k$ vertices. $\endgroup$ – Yuval Filmus Dec 19 '17 at 8:30
  • $\begingroup$ Perhaps you are able to find any tree on $k$ vertices, but this requires proof. But first I'd like to ascertain that this is actually want you are trying to prove. $\endgroup$ – Yuval Filmus Dec 19 '17 at 10:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.