  We present all-multiplicity evidence that the tree-level S-matrix of gluons
and gravitons in heterotic string theory can be reduced to color-ordered
single-trace amplitudes of the gauge multiplet. Explicit amplitude relations
are derived for up to three gravitons, up to two color traces and an arbitrary
number of gluons in each case. The results are valid to all orders in the
inverse string tension $\alpha'$ and generalize to the ten-dimensional
superamplitudes which preserve 16 supercharges. Their field-theory limit
results in an alternative proof of the recently discovered relations between
Einstein-Yang-Mills amplitudes and those of pure Yang-Mills theory.
Similarities and differences between the integrands of the Cachazo-He-Yuan
formulae and the heterotic string are investigated.
