  We present new relations for scattering amplitudes of color ordered gluons
and gravitons in Einstein-Yang-Mills theory. Tree-level amplitudes of arbitrary
multiplicities and polarizations involving up to three gravitons and up to two
color traces are reduced to partial amplitudes of pure Yang-Mills theory. In
fact, the double-trace identities apply to Einstein-Yang-Mills extended by a
dilaton and a B-field. Our results generalize recent work of Stieberger and
Taylor for the single graviton case with a single color trace. As the
derivation is made in the dimension-agnostic Cachazo-He-Yuan formalism, our
results are valid for external bosons in any number of spacetime dimensions.
Moreover, they generalize to the superamplitudes in theories with 16
supercharges.
