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

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Mar 10, 2020 at 10:39
  • $\begingroup$ 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? $\endgroup$ Commented Mar 10, 2020 at 12:11
  • 1
    $\begingroup$ 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.) $\endgroup$ Commented Mar 10, 2020 at 16:08
  • $\begingroup$ @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? $\endgroup$ Commented Mar 11, 2020 at 20:33
  • $\begingroup$ @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$ $\endgroup$ Commented Mar 12, 2020 at 10:18

1 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$.
  • $\begingroup$ Thanks for your construction!! $\endgroup$ Commented Mar 21, 2020 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.