Trees contained in every orientation of a graph (Q2138584)

Summary: 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\). \textit{S. A. Burr} [in: Proceedings of the eleventh south-eastern conference on combinatorics, graph theory and computing, held at Florida Atlantic University, Boca Raton, Florida, from March 3--7, 1980. Vols. I, II. Winnipeg, MB: Utilitas Mathematica Publishing Inc. 227--239 (1980; Zbl 0453.05022)] 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\).