"Roundtrip"-chromatic number of (connected) graphs

Question

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

Answer 1

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