Starting point of roundtrip coloring in connected graphs

Question

This is a subquestion for an older question 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 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')$?

Answer 1

My answer to your other question 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) whereas $\chi(r,v_1') = 4$.