"Roundtrip"-chromatic number of (connected) graphs 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:


*

*$r$ is surjective,

*$\{r(k), r(k+1)\} \in E$ for all $k \in \{0, \ldots, n-1\}$, and

*$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. 


*

*$c_{r,v}(v) = 1$;

*since $r$ is surjective, $v$ appears somewhere on $r$, so take the next point, $v^*$ and if $c_{r,v}(v^*)$ has not been defined yet (which it hasn't in the first iteration), assign to it the smallest positive integer $m$ such that none of those neighbors of $v^*$ that already have been assigned a color, have color $m$;

*Repeat Step 2 until all points have been assigned a color.


Set $\chi_{r,v}(G) = \max(\text{im}(c_{r,v}))$ and let $\chi_r(G) = \min\{\chi_{r,v}(G):v \in V\}$ be the roundtrip coloring number with respect to $r$.
Question. Is there a global constant $N_0\in \mathbb{N}$ such that whenever $G$ is a finite connected graph, then $\chi_r(G) \leq \chi(G)+N_0$?
 A: There are graphs with $\chi(G) = 4$ and arbitrarily large $\chi_r(G)$ (linear in the number of vertices) for a badly chosen roundtrip $r$.
A family of examples can be constructed as follows: For an even integer $n \geq 4$, consider the graph with vertex set $\{v_i,v_i',u_i,u_i'\mid 1 \leq i \leq n\}$ and edges 


*

*$v_iv_j'$ and $u_iu_j'$ for $i \neq j$,

*$v_iv_{i+1}$, $v_i'v_{i+1}'$, $u_iu_{i+1}$, and $u_i'u_{i+1}'$ for $1 \leq i < n$, and 

*$v_n'u_1$ and $u_n'v_1$.


In other words, the induced subgraph on the vertices $v_i,v_i'$ is a complete bipartite graph minus a matching plus a spanning path on both sides, and similarly for $u_i,u_i'$, and there are two additional edges connecting these two graphs. 
It is easy to see that $\chi (G_n) = 4$: Colour the path spanned by $v_i$ and $u_i'$ with colours 1 and 2 and the path spanned by $u_i$ and $v_i'$ with colours 3 and 4. Fewer colours are not possible because $G_n$ contains copies of $K_4$.
For $\chi_r(G_n)$ consider the roundtrip $r$ given by
$$
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', u_1, u_2, u_1', u_2', u_3, u_4, u_3', u_4', \dots, u_n', v_1.
$$
Without loss of generality assume that the chosen starting point $v$ is $u_i$ or $u_i'$, so the vertices $v_i$ and $v_i'$ are visited in order $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'$. It is not hard to check inductively that


*

*$v_1$ and $v_2$ are coloured with colours $\{1,2\}$ (not necessarily in that order),

*$v_i'$ receives the same colour as $v_i$,

*for $i \geq 3$, the colour of $v_i$ (and thus also $v_i'$) is $i$.

