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. 


1. $c\_{r,v}(v) = 1$;
2. 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$;
3. 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$?



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


