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$ – darij grinberg Feb 15 '17 at 9:22
  • $\begingroup$ Right - maybe I didn't write this in most elegant way! I will add your description. $\endgroup$ – Dominic van der Zypen Feb 15 '17 at 9:58

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, privacy policy and cookie policy

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