Oriented trees in n-chromatic digraphs

Oriented trees in n-chromatic digraphs

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless simple digraph, allowing opposite arcs but not repeated arcs in one direction. Its underlying undirected graph $U(D)$ has an edge $uv$ whenever at least one of $uv,vu$ is an arc. The chromatic number used here is $\chi(D)=\chi(U(D))$: adjacent vertices must have different colours, regardless of arc direction. It is not the dichromatic number defined by acyclic colour classes.

An oriented tree $T$ is obtained by orienting each edge of a finite undirected tree. Its order is $|V(T)|$. A copy of $T$ as a subdigraph of $D$ means an injective map $\varphi:V(T)\to V(D)$ such that $xy\in A(T)$ implies $\varphi(x)\varphi(y)\in A(D)$. Other arcs among the image vertices are allowed, so this is not an induced-copy condition.

The conjecture asks whether, for every integer $k\ge2$, every digraph $D$ with \[ \chi(D)\ge2k-2 \] contains every oriented tree of order $k$ in this sense. The quantifier "every" includes all tree shapes and all choices of directions.

The proposed threshold is sharp: a regular tournament on $2k-3$ vertices has ordinary chromatic number $2k-3$ but every outdegree is $k-2$, so it cannot contain the oriented star with one vertex pointing to $k-1$ leaves. No bound on indegrees, outdegrees, or the total order of $D$ is assumed beyond the chromatic hypothesis.

Short English statement

Does ordinary chromatic number at least 2k−2 force a digraph to contain every orientation of every k-vertex tree?

Research attempt: all stars and a semidegree embedding lemma

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. The chromatic number is that of the underlying graph, and tree copies need not be induced. Bessy, Gonçalves and Reinald [S3] obtained a subquadratic sufficient chromatic bound. Fan--Lu--Chen [S4], posted in September 2026, announce a near-linear $O(k\log k)$ bound. This is a preprint result and still differs from the exact conjectured $2k-2$ threshold. Here the work establishes the threshold for every oriented star and identifies why a straightforward greedy extension does not handle general trees.

1. Removing opposite arcs without losing chromatic number.

Choose exactly one direction from each opposite pair, keeping all other arcs. This produces an oriented graph $D'$ with precisely the same underlying undirected graph as $D$. Every tree found in $D'$ also occurs in $D$. We may therefore assume in the proofs below that incoming and outgoing neighbour sets are disjoint. This observation is essential when the leaves of a mixed star must be distinct.

2. Stars with all arcs in one direction.

A graph of chromatic number at least $2k-2$ has a vertex-critical subgraph of chromatic number $2k-2$. Every vertex of that subgraph has degree at least $2k-3$: otherwise a colouring of its deletion with $2k-3$ colours extends to the vertex. Its orientation has at least $(2k-3)|V|/2$ arcs. Average outdegree is consequently at least $k-3/2$, and some integer outdegree is at least $k-1$. The vertex and any $k-1$ of its outneighbours form the required outward star. Applying the same argument to indegrees gives the inward star. The critical subgraph is used only for counting; additional arcs among leaves are harmless under the non-induced convention.

3. Every mixed star.

Let the centre have $a\ge1$ outgoing leaves and $b\ge1$ incoming leaves, where $a+b=k-1$. Suppose no vertex satisfies both $d^+\ge a$ and $d^-\ge b$. Put \[ X=\{v:d^+(v)\le a-1\},\qquad Y=V\setminus X. \] Every vertex of $Y$ then has indegree at most $b-1$. For every nonempty $W\subseteq X$, the induced underlying graph has at most $(a-1)|W|$ edges, by counting outgoing arcs within $W$. Its average degree is at most $2a-2$, so it has a vertex of degree at most that number. Repeated deletion and greedy recolouring show $\chi(D'[X])\le2a-1$. Counting incoming arcs gives, in exactly the same way, $\chi(D'[Y])\le2b-1$.

Using disjoint palettes on the two sets yields $\chi(D')\le2a+2b-2=2k-4$, a contradiction. Thus the required centre exists. Its incoming and outgoing neighbour sets are disjoint in $D'$, so selecting $a$ and $b$ leaves gives an injective star copy. In fact mixed stars follow already from $\chi\ge2k-3$. Since every tree on at most three vertices is a star, this also proves all orientations in the cases $k=2,3$ of the original statement.

4. A sufficient extension condition and its obstruction.

If a digraph has both minimum indegree and minimum outdegree at least $k-1$, every oriented $k$-vertex tree embeds greedily. Root the tree and process children after their parents. When embedding a child, at most $k-2$ already occupied vertices other than the parent must be avoided. The parent has at least $k-1$ neighbours in the required direction, leaving an unused choice. No arcs between different branches are prohibited.

Ordinary chromatic number does not furnish this semidegree condition, even after passage to an induced subgraph. A transitive tournament has arbitrarily large chromatic number, but every nonempty induced subtournament has a source and a sink. It nevertheless contains every oriented tree of suitable order, by placing a topological ordering of the tree in its linear order. Thus the obstruction is to the proposed extraction argument, not to the conjecture itself.

Verification, gap and final status.

The script [S9] checks the regular-tournament star obstruction below the proposed threshold and the source/sink obstruction just used. The proofs cover all star sizes without computation. The first remaining gap is coordinating extension at several internal tree vertices under a chromatic hypothesis alone. No such invariant is provided. Full target: UNRESOLVED; all oriented stars are verified.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3260 (OPG-46167), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Oriented trees in n-chromatic digraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/oriented_trees_in_n_chromatic_digraphs.
• S3 Stéphane Bessy, Daniel Gonçalves and Amadeus Reinald, Oriented trees in $O(k\sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr's conjecture. https://arxiv.org/abs/2402.19351.
• S4 Liangdong Fan, Junying Lu and Yaojun Chen, A near-linear upper bound for Burr's conjecture (preprint, 16 September 2026). https://arxiv.org/abs/2609.18175.
• S9 GPT-6 Astra Ultra, exact finite checks accompanying this attempt (2 October 2026). Repository script, Python standard library only. scripts/check_attempt_batch03_digraphs_2026_10_02.py.