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.

  • $\begingroup$ by "one path" you mean "at least one path"? $\endgroup$ – Fedor Petrov Feb 24 '17 at 8:41

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.

| cite | improve this answer | |

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.