We consider the problem of fair cost allocation for traveling
salesman games for which the triangle inequality holds. We
give examples showing that the core of such games may be
empty, even for the case of Euclidean distances. On the
positive side, we develop an LP-based allocation rule
guaranteeing that no coalition pays more than $\alpha$
times its own cost, where $\alpha$ is the ratio between
the optimal TSP-tour and the optimal value of its Held-Karp
relaxation (which is also known as the solution of the
"subtour polytope"). A well-known conjecture states that
$\alpha \leq 4/3$. We also exhibit examples showing that
this ratio cannot be improved below 4/3.