Trees contained in every orientation of a graph (Q2138584)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Trees contained in every orientation of a graph |
scientific article |
Statements
Trees contained in every orientation of a graph (English)
0 references
12 May 2022
0 references
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\).
0 references
oriented graphs
0 references
anti-dominating set
0 references