Open Problem Garden

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Directed Graphs

Keywords:

Recomm. for undergrads: no

Posted	by:	fhavet
	on:	February 25th, 2013

Conjecture Every digraph with chromatic number at least $2k-2$ contains every oriented tree of order $k$ as a subdigraph.

The conjectured bound is best possible, because a regular tournament of order $2k-3$ does not contain the oriented tree consisting of a vertex dominating $k-1$ leaves.

Let $f$ be the function $f$ such that every oriented tree of order $k$ is $f(k)$ -universal, that is contained in every digraph with chromatic number at least $f(k)$ . Burr proved that $f(k) \leq (k-1)^2$ . This was slightly improved by Addario-Berry et al. [AHL+] who proved $f(k)\leq k^2/2-k/2+1$ .

Burr's conjecture has been proved only in few particular cases of digraphs: tournaments, and acyclic digraphs. Kühn, Mycroft, and Osthus [KMS] showed that every oriented tree of order $k$ is contained in every tournament of order $2k-2$ for all sufficiently large $k$ (so proving a Conjecture of Sumner); Addario-Berry et al. [AHL+] proved that every acyclic digraph with chromatic number $k$ contains every oriented tree of order $k$ .

Burr's conjecture or some approximation have been also proved for special classes of trees. Gallai-Roy's celebrated theorem states that every directed path of order $k$ is $k$ -universal; El-Sahili [E] proved that every oriented path of order $4$ is $4$ -universal and that the antidirected path of order $5$ is $5$ -universal; Addario-Berry, Havet, and Thomassé [AHT] showed that every oriented path of order $k$ whose vertex set can be partioned into two directed paths is $k$ -universal; Addario-Berry et al. [AHL+] showed that antidirected trees (oriented trees in which every vertex has in-degree $0$ or out-degree $0$ ) are $5k$ -universal.

Havet, generalizing a conjecture of Havet and Thomassé (see [H]) on tournaments, conjectured that the following could also be true.

Conjecture Every digraph with chromatic number at least $k+\ell+1$ contains every oriented tree of order $k$ with $k$ leaves.

Bibliography

[AHL+] L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313(8):967-974, 2013.

[AHT] L. Addario-Berry, F. Havet, and S. Thomassé, Paths with two blocks in $n$ -chromatic digraphs, J. of Combinatorial Theory Ser. B, 97 (2007), 620--626.

* [B] A. Burr, Subtrees of directed graphs and hypergraphs, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Congr. Numer., 28 (1980), 227--239.

[H] F. Havet, Trees in tournaments. Discrete Mathematics 243 (2002), no. 1-3, 121--134.

[KOM] D. Kühn, D. Osthus, and R. Mycroft, A proof of Sumner's universal tournament conjecture for large tournaments, Proceedings of the London Mathematical Society 102 (2011), 731--766.

* indicates original appearance(s) of problem.

add new comment

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity