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.

  • $\begingroup$ So, $c_b $ is the coloring greedily constructed by traversing the graph in the order $b $, right? $\endgroup$ Feb 15, 2017 at 9:22
  • $\begingroup$ Right - maybe I didn't write this in most elegant way! I will add your description. $\endgroup$ Feb 15, 2017 at 9:58

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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