This is a subquestion for an [older question](https://mathoverflow.net/questions/354548/roundtrip-chromatic-number-of-connected-graphs) about a certain kind of greedy coloring.


Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a *roundtrip of $G$* we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:


1. $r$ is surjective,
2. $\{r(k), r(k+1)\} \in E$ for all $k \in \{0, \ldots, n-1\}$, and
3. $r(0) = r(n)$.


An easy inductive argument shows that we can select $n$ such that $n \leq 2|G|$.


Given a roundtrip $r$ and a vertex $v\in V$, we assign a *roundtrip coloring $c\_{r,v}:V\to\mathbb{N}$ of $G$, starting at $v$* in the following manner: Start at $v$, proceed along the roundtrip $r$ and [greedy-color](https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring) every uncolored vertex along the way, until every vertex has been colored. Let $\chi(r,v)$ be the number of colors used.


**Question.** What is an example of a connected graph $G=(V,E)$ and $v\neq v'\in V$ such that $\chi(r,v)\neq \chi(r,v')$?



Starting point of roundtrip coloring in connected graphs
My answer to your [other question](https://mathoverflow.net/questions/354699/starting-point-of-roundtrip-coloring-in-connected-graphs?noredirect=1&lq=1) can be modified to give a family of graphs and a roundtrip such that the difference $\chi(r,v)-\chi(r,v')$ is linear in the number of vertices. Let $G$ be a graph with vertex set $\{v\_i,v\_i'\mid 1 \leq i \leq n\}$ where $n$ is an even integer and edges $v\_iv\_j'$ for $i \neq j$ and $v\_iv\_{i+1}$ and $v\_i'v\_{i+1}'$ for $1 \leq i < n$.


In other words, take a complete bipartite graph, delete a perfect matching, and add the edges of a spanning path in each of the bipartite parts.


Let $r$ be the roundtrip
$$
v\_1,v\_2,v\_1',v\_2',v\_3,v\_4,v\_3',v\_4', \dots, v\_{n-1},v\_n,v\_{n-1}',v\_n',v\_1.
$$
Then $\chi(r,v\_1) = n$ (like in my answer to your [other question](https://mathoverflow.net/questions/354699/starting-point-of-roundtrip-coloring-in-connected-graphs?noredirect=1&lq=1)) whereas $\chi(r,v\_1') = 4$.


