# Chromatic paths in Hamiltonian graphs

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). A chromatic path is a chromatic bijection that is also a path.

• So, $c_b$ is the coloring greedily constructed by traversing the graph in the order $b$, right? – darij grinberg Feb 15 '17 at 9:22
• Right - maybe I didn't write this in most elegant way! I will add your description. – Dominic van der Zypen Feb 15 '17 at 9:58