**Question.** If $G$ is a Hamiltonian, does it contain a chromatic path visiting all the vertices? (I define the term "chromatic path" below.)




---


We denote by $\mathbb{N}$ the set of positive integers and set $[n] = \{1,\ldots,n\}$ for $n\in\mathbb{N}$.


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](https://en.wikipedia.org/wiki/Greedy_coloring#Optimal_ordering)). A *chromatic path* is a chromatic bijection that is also a [path](https://en.wikipedia.org/wiki/Path_(graph_theory)).



Chromatic paths in Hamiltonian graphs
No, here is a counterexample.


Take a cycle on 18 vertices and add three triangles between vertices 1,3,5 and 7,9,11 and 13,15,17. This graph has chromatic number 3, and all hamiltonian paths follow the cycle. Each of these hamiltonian paths will result in most degree 2 vertices receiving color 1, leading to the use of 4 colors total.


