# Starting point of roundtrip coloring in connected graphs

This is a subquestion for an older question about a certain kind of greedy coloring.

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: Start at $$v$$, proceed along the roundtrip $$r$$ and greedy-color every uncolored vertex along the way, until every vertex has been colored. Let $$\chi(r,v)$$ be the number of colors used.

Question. What is an example of a connected graph $$G=(V,E)$$ and $$v\neq v'\in V$$ such that $$\chi(r,v)\neq \chi(r,v')$$?

## 1 Answer

My answer to your other question can be modified to give a family of graphs and a roundtrip such that the difference $$\chi(r,v)-\chi(r,v')$$ is linear in the number of vertices. Let $$G$$ be a graph with vertex set $$\{v_i,v_i'\mid 1 \leq i \leq n\}$$ where $$n$$ is an even integer and edges $$v_iv_j'$$ for $$i \neq j$$ and $$v_iv_{i+1}$$ and $$v_i'v_{i+1}'$$ for $$1 \leq i < n$$.

In other words, take a complete bipartite graph, delete a perfect matching, and add the edges of a spanning path in each of the bipartite parts.

Let $$r$$ be the roundtrip $$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',v_1.$$ Then $$\chi(r,v_1) = n$$ (like in my answer to your other question) whereas $$\chi(r,v_1') = 4$$.