Oriented trees in digraphs.

Louigi Addario-Berry (1) , Frédéric Havet (2) , Claudia Linhares Sales (3) , Bruce Reed , Stéphan Thomassé (4)

1 Department of Mathematics and Statistics [Montréal]
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
3 ParGO - Parallelism, Graphs and Optimization Research Group
4 ALGCO - Algorithmes, Graphes et Combinatoire

Let f (k) be the smallest integer such that every f (k)-chromatic digraph contains every oriented tree of order k. Burr proved that f (k) ≤ (k − 1)^2 and conjectured f (k) = 2n − 2. In this paper, we give some sufficient conditions for an n-chromatic digraphs to contains some oriented tree. In particular, we show that every acyclic n-chromatic digraph contains every oriented tree of order n. We also show that f (k) ≤ k^2/2 − k/2 + 1. Finally, we consider the existence of antidirected trees in digraphs. We prove that every antidirected tree of order k is containedinevery(5k−9)-chromaticdigraph. Weconjecturethatif|E(D)|>(k−2)|V(D)|,thenthedigraph D contains every antidirected tree of order k. This generalizes Burr's conjecture for antidirected trees and the celebrated Erdo ̋s-So ́s Conjecture. We give some evidences for our conjecture to be true.

Mots clés: universaldigraph; orientation of graphs; digraph colouring

Domaines: Mathématique discrète [cs.DM]

Louigi Addario-Berry, Frédéric Havet, Claudia Linhares Sales, Bruce Reed, Stéphan Thomassé. Oriented trees in digraphs.. [Research Report] RR-7502, INRIA. 2011. ⟨inria-00551133⟩