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$?

2more comments