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 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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