3
$\begingroup$

This question is from a home assignment but it makes no sense to me.

Construct a sequence of trees $(T_n)^∞_{n=1}$ with an ordering of their vertices such that the greedy colouring algorithm uses n colours to find a proper colouring of $T_n$.

From what I can tell, the greedy coloring algorithm always ends up using just two colors when coloring a tree regardless of the ordering of vertices but this question assumes otherwise. Am I wrong? I'm completely stuck on this.

$\endgroup$
9
  • $\begingroup$ the greedy coloring algorithm always ends up using just two colors when coloring a tree regardless of the ordering of vertices What if the tree is a path of $4$ vertices, and you color the two end vertices first? How many colors do you end up using in that case? $\endgroup$
    – bof
    Jan 4, 2017 at 19:34
  • $\begingroup$ @bof That still only uses 3 colors for a tree with 4 vertices though, right? $\endgroup$
    – smellinor
    Jan 4, 2017 at 19:38
  • $\begingroup$ The problem doesn't say that $T_n$ is a tree with $n$ vertices. Hint: $T_{n+1}$ may have twice as many vertices as $T_n$. $\endgroup$
    – bof
    Jan 4, 2017 at 19:41
  • $\begingroup$ @bof No, but I sort of assumed so based on our lecture notes. The professor uses notation that implies that $T_n$ has $n$ vertices. Partial credit is offered for doing the coloring for $n=2,3,4,5$ too, so it sort of makes sense. $\endgroup$
    – smellinor
    Jan 4, 2017 at 19:48
  • $\begingroup$ Your title asks a different question to the one in the body. The number of vertices is specified in the first one and not in the second. $\endgroup$ Jan 4, 2017 at 19:52

1 Answer 1

2
$\begingroup$

Such a tree $T_n$ must have at least $2^{n-1}$ vertices. Here is a simple recursive construction where the tree $T_n$ has exactly $2^{n-1}$ vertices. In each case we order the vertices so that vertices of lower degree are colored before vertices of higher degree.

For $n=1$ let $T_1=P_1=K_1$.

For $n=2$ let $T_2=P_2=K_2$.

For $n=3$ let $T_3=P_4$; it has vertices $v_1,v_2,v_3,v_4$ and edges $v_1v_2,v_2v_3,v_3v_4$.

For $n=4$ start with the tree $T_3$ and add new vertices $v_1',v_2',v_3',v_4'$ and edges $v_1v_1',v_2v_2',v_3v_3',v_4v_4'$.


Edit. As requested in a comment, here is a detailed description and a proof.

Let $W_1,W_2,W_3,\dots$ be disjoint sets with $|W_1|=1$ and $|W_n|=2^{n-2}$ for $n\ge2$, so that $|W_n|=|W_1\cup\cdots\cup W_{n-1}|$ for $n\ge2$. Let $V_n=W_1\cup\cdots\cup W_n$.

Let $E_1=\varnothing$. For $n\ge2$ let $M_n$ be a matching between $W_n$ and $V_{n-1}=W_1\cup\cdots\cup W_{n-1}$ and let $E_n=E_{n-1}\cup M_n=M_2\cup\cdots\cup M_n$.

Plainly $T_n=(V_n,E_n)$ is a tree of order $2^{n-1}$. If $v\in W_i$ and $n\ge i$, then in the tree $T_n$ the vertex $v$ has no neighbors in $W_i$, exactly one neighbor in $W_j$ for each $j$ such that $i\lt j\le n$, and, if $i\ge2$, exactly one neighbor in $W_1\cup\cdots\cup W_{i-1}$; thus $$\deg_{T_n}v=\begin{cases} n-1\quad\quad\text{ if }\ \ i=1,\\ n-i+1\ \ \text{ if }\ \ i\ge2.\\ \end{cases}$$ I claim that, if the vertices of $T_n$ are ordered so that vertices of lower degree precede vertices of higher degree, then the greedy coloring of $T_n$ uses $n$ colors.

The proof is by induction on $n$. The claim is clearly true for $T_1=K_1$ and $T_2=K_2$. Suppose $n\ge3$. We start by coloring the leaves of $T_n$; these are precisely the elements of $W_n$, which is an independent set, so they all get the same color, call it red. It remains to color the vertices of $T_{n-1}$. Since $$\deg_{T_{n-1}}v=\deg_{T_n}v-1$$ for $v\in V_{n-1}$, it follows from the inductive hypothesis that the greedy algorithm on $T_n$ will use $n-1$ colors on the vertices of $T_{n-1}$. Since each vertex of $T_{n-1}$ has a neighbor in $W_n$, no vertex of $T_{n-1}$ is colored red, so a total of $n$ colors are used on $T_n$.

$\endgroup$
2
  • $\begingroup$ i figured out how to construct n=5, 6, etc according to the pattern; and it does work when i color using order from low to high degree by hand--but is there a more rigorous way to write/show that how this ordering leads to the usage of n colours? thanks $\endgroup$ Mar 29, 2021 at 17:49
  • 1
    $\begingroup$ upvoted, thank you so much $\endgroup$ Apr 6, 2021 at 3:45

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.