Arbitrary Orientations of Hamilton Cycles in Oriented Graphs

  • Luke Kelly

Abstract

We use a randomised embedding method to prove that for all $\alpha>0$ any sufficiently large oriented graph $G$ with minimum in-degree and out-degree $\delta^+(G),\delta^-(G)\geq (3/8+\alpha)|G|$ contains every possible orientation of a Hamilton cycle. This confirms a conjecture of Häggkvist and Thomason.

Published
2011-09-20
Article Number
P186