Let $G$ be a graph with $n$ vertices and let $T(G)$ be the set of all bijections from vertices $V(G)$ of $G$ to the set $\{1,\dots,n\}$. Let $E(G)$ be as ususal the set of edges of $G$. Is the following problem well-known? Has it a well-accepted name in the litratures? Do you know of any result about it?

Compute $$\min_{\sigma \in T(G)} \max_{vw \in E(G)} |\sigma(v)-\sigma(w)|$$

  • $\begingroup$ At the risk of sending you on a 200-page wild goose chase, I'd suggest taking a look at Joe Gallian's Dynamic Survey of Graph Labeling, combinatorics.org/Surveys/ds6.pdf $\endgroup$ Nov 4, 2011 at 20:36
  • $\begingroup$ It might help if you made some comments about where the problem comes from. My guess is that it is not particularly tractable algorithmically. $\endgroup$
    – Igor Rivin
    Nov 4, 2011 at 21:28

2 Answers 2


I was thinking, that has a name, that has a name, and mathoverflow knew it, it was on the related column on the right. The invariant is often called the bandwidth of a graph. As Professor Rivin already mentioned it is NP-complete to compute it. There is however a pretty $(log n)^c$-approximation algorithm by Fiege, he generalizes Bourgain's embedding theorem and the London-Linial-Rabonovich approximation of the sparsets cut, by first generalizing bilipschitz distortion to something he calls "volume preserving embeddings". It is informally explained in chapter 15 of Matousek's "Lectures on Discrete Geometry", that is available online.


For a very similar problem, see http://www2.research.att.com/~yifanhu/PUB/map_color.pdf Luckily, the authors discuss your question in Section 2 (yes, it is computationally hard, and it seems to have more than one name.).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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