SOLUTION:
A linear ordering of V, i.e. a one-to-one function
.
MEASURE:
The bandwidth of the ordering, i.e.
.
Bad News:
Not approximable within 1.5
for any
[81].
Not approximable with an absolute error
guarantee of
for every
[295].
Comment:
Approximable within 3 if every vertex has degree
[296].
Approximable within
if G is a caterpillar [234].
Approximable within 2 if G is asteroidal triple-free [326].
Not approximable within 1.332
for any
if G is a tree
[81].