Skip to main content
added 77 characters in body
Source Link

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 it$b$ the mapgreedy coloring $c_b:[n] \to [n]$, which is recursively defined$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.

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 it the map $c_b:[n] \to [n]$, which is recursively defined by:

  • $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.

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.

added 4 characters in body
Source Link

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>1$$n\geq 1$ vertices, and let $b:[n]\to V$ be a bijection. We assign to it the map $c_b:[n] \to [n]$, which is recursively defined by:

  • $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}(b) = [\chi(G)]$$\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.

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>1$ vertices, and let $b:[n]\to V$ be a bijection. We assign to it the map $c_b:[n] \to [n]$, which is recursively defined by:

  • $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}(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.

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 it the map $c_b:[n] \to [n]$, which is recursively defined by:

  • $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.

Source Link

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>1$ vertices, and let $b:[n]\to V$ be a bijection. We assign to it the map $c_b:[n] \to [n]$, which is recursively defined by:

  • $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}(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.