Label distance number and chromatic number of a graph

Question

Let $n\in\mathbb{N}$ be a positive integer, and let $[n] = \{1,\ldots,n\}$. We set $S_n$ for the set of all bijections $\varphi:[n]\to [n]$.

Let $G= ([n], E)$ be a simple, undirected graph, and let $\varphi\in S_n$ We define the label distance number of $G$ in the following way: $$\lambda(G) = \min\big\{\max\{|\varphi(v)-\varphi(w)|:\{v,w\}\in E\}: \varphi\in S_n\big\}.$$

Conjecture: if $n$ is a positive integer, and $G, H$ are graphs with $V(G) = V(H) = [n]$ and $\chi(G) < \chi(H)$, then $\lambda(G)\leq \lambda(H)$.

Is this conjecture true?

I would also be interested in knowing whether there is an established name for what I call label distance number.

Answer 1

The cycle on five vertices has chromatic number 3 and bandwidth 2. The complete bipartite graph with blocks 2 and 3 has chromatic number 2 and bandwidth 3.