Trees Contained in Every Orientation of a Graph

Abstract

For every graph $G$, let $t(G)$ denote the largest integer $t$ such that every oriented tree of order $t$ appears in every orientation of $G$. In 1980, Burr conjectured that $t(G)\geq 1+\chi(G)/2$ for all $G$, and showed that $t(G)\geq 1+ \lfloor\sqrt{\chi(G)}\rfloor$; this bound remains the state of the art, apart from the multiplicative constant. We present an elementary argument that improves this bound whenever $G$ has somewhat large chromatic number, showing that $t(G)\geq \lfloor \chi(G)/\log_2 v(G)\rfloor$ for all $G$.