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.


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.

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