# “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:

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

• Do you have an example where you do not have equality of $\chi_r(G)$ and $\chi(G)$? This seems to be greedy coloring restricted to those orderings of the vertices in which the ordering respects adjacency. I would not be surprised if the answer to your question is negative, but I can't think of an example at the moment. – Carl-Fredrik Nyberg Brodda Mar 10 at 10:39
• The process has not been well-defined. To which vertex $v$ and to which of its neighbours should we apply Step 2 at a certain moment? – Ilya Bogdanov Mar 10 at 12:11
• That's right, it is greedy coloring applied to a round-trip, and applied repeatedly for all the points $v\in V(G)$ and then taking the minimal resulting greedy chromatic number. Sorry for the bad description, Ilya, and thanks for the correct term @Carl-FredrikNybergBrodda. - I haven't been able to find an example of a connected graph with $\chi_r(G) > \chi(G)$, but there must be - otherwise this would be a polynomial time coloring (which is I think not inconsistent / impossible but it's unlikely this would be one.) – Dominic van der Zypen Mar 10 at 16:08
• @DominicvanderZypen I don't see immediately how it would be polynomial time. Surely enumerating all roundtrips is at least exponential, or am I missing something obvious? – Carl-Fredrik Nyberg Brodda Mar 11 at 20:33
• @Carl-FredrikNybergBrodda You don't enumerate all round-trips, but pick just one, say $r$, and then you perform the greedy coloring along $r$ for every vertex $v\in V$ – Dominic van der Zypen Mar 12 at 10:18

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