Non-chromatic paths in Hamiltonian graphs

Question

What is an example of a Hamiltonian graph $G=(V,E)$ such that there is one path visiting all vertices that is not chromatic (definition see below)?

---

Let $G= (V,E)$ be a simple undirected graph on $n\geq 1$ vertices, and let $b:[n]\to V$ be a bijection. We assign to $b$ the greedy coloring $c_b$ constructed by traversing the graph in the order $b$. Formally, with recursive definition of $c_b:[n] \to [n]$:

• $c_b(1) = 1$;
• if $k\in[n]$ and $k>1$ let $$c_b(k) = \min\:\big(\mathbb{N}\setminus\{c_b(j): j \in [k-1]\land \{b(j),b(k)\}\in E\}\big).$$

We call $b$ chromatic if $\text{im}(c_b) = [\chi(G)]$. For every graph there is a chromatic bijection (see here). A chromatic path is a chromatic bijection that is also a path.

Answer 1

Counterexample. Let $G$ be the graph with vertices $v_1,v_2,v_3,v_4,v_5,v_6$ and edges $v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_1,v_1v_5,v_4v_6.$

The graph $G$ is Hamiltonian, since $v_1,v_2,v_3,v_4,v_5,v_6,v_1$ is a Hamiltonian cycle.

The graph $G$ is $3$-chromatic; for a proper coloring, we may color $v_1$ and $v_4$ red, $v_2$ and $v_5$ white, $v_3$ and $v_6$ blue.

The path $v_1,v_2,v_3,v_4,v_5,v_6$ is not chromatic.