The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.
For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.
Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$.
Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.
Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.
Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.
This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$.
Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.
Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$).
The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component.
If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$.
Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.
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$.
Best Answer
Given a minimal coloring $c:V(G)\rightarrow\{1,2,\ldots,\chi(G)\}$, simply order the vertices in the queue so that all the vertices with $c(v)=1$ come first, followed by those with $c(v)=2$, and so on. When the vertices are removed from the queue, each will be assigned a new color $c'(v)$. Since none of the vertices with $c(v)=1$ are adjacent to each other, they will all have $c'(v)=c(v)=1$. Next, none of the vertices with $c(v)=2$ are adjacent to each other, so they will all have either $c'(v)=1$ (if they have no neighbors in the first batch) or $c'(v)=2$; that is, $c'(v)\le c(v)$ for $c(v)\le 2$. And so on, by induction; we conclude that $c'(v) \le c(v)$ for all $v$. So $c'$ has no more colors than $c$; and since $c$ was already a minimal coloring, $c'$ must have exactly $\chi(G)$ colors.