Polynomial Compressibility and Forbidden Oriented Forests

Abstract

For a nonempty acyclic oriented graph $H$, let $p(H)$ be the order of a longest directed path and let $\tau (H)$ be the least positive integer $n$ such that $H$ admits a homomorphism to every tournament of order $n$. For all $p\ge 3$ and $g\ge 1$, we construct a connected acyclic oriented graph $H$ with underlying girth greater than $g$, absolute and relative oriented clique numbers equal to three, and \[ p(H)=p,\qquad τ(H)=r_{\mathrm{tr}}(p), \] where $r_{\mathrm{tr}}(p)=2^{\Theta (p)}$ is the tournament Ramsey number for a transitive $p$-vertex tournament. This disproves the conjectured polynomial bounds under bounded absolute or relative oriented clique number. It also shows that a forbidden graph can yield a polynomially $\tau$-bounded class only if its underlying graph is a forest. For fixed $g$, the least order of these examples is bounded by a polynomial in $p$. A separate construction gives maximum in- and outdegree $O(p^2)$, uniformly in $g$. For $p=4$, the least order is $2^{\Theta (g)}$. We also establish polynomial $\tau$-boundedness for every orientation of the two four-vertex trees. The pure-claw case follows from the known $O(p^4)$ bound. We obtain the bound $2p-2$ for mixed claws and one-turn orientations of $P_4$ when $p\ge 2$, and bounds $4$ and $3p-2$ for the directed and alternating orientations of $P_4$, respectively. In the alternating case, $\tau (H)=p(H)$ when the underlying graph is triangle-free.

arXiv comment16 pages