# Oriented trees in digraphs

2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Let $f(k)$ be the smallest integer such that every $f(k)$-chromatic digraph contains every oriented tree of order $k$. Burr proved $f(k)\leq (k-1)^2$ in general, and he conjectured $f(k)=2k-2$. Burr also proved that every $(8k-7)$-chromatic digraph contains every antidirected tree. We improve both of Burr's bounds. We show that $f(k)\leq k^2/2-k/2+1$ and that every antidirected tree of order $k$ is contained in every $(5k-9)$-chromatic digraph. We make a conjecture that explains why antidirected trees are easier to handle. It states that if $|E(D)| > (k-2) |V(D)|$, then the digraph $D$ contains every antidirected tree of order $k$. This is a common strengthening of both Burr's conjecture for antidirected trees and the celebrated Erd\H{o}s-Sós Conjecture. The analogue of our conjecture for general trees is false, no matter what function $f(k)$ is used in place of $k-2$. We prove our conjecture for antidirected trees of diameter 3 and present some other evidence for it. Along the way, we show that every acyclic $k$-chromatic digraph contains every oriented tree of order $k$ and suggest a number of approaches for making further progress on Burr's conjecture.
Type de document :
Article dans une revue

Littérature citée [25 références]

https://hal.inria.fr/hal-00821609
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:07:49
Dernière modification le : lundi 11 février 2019 - 16:40:02

### Fichier

ortree-final.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Louigi Addario-Berry, Frédéric Havet, Claudia Linhares Sales, Bruce Reed, Stéphan Thomassé. Oriented trees in digraphs. Discrete Mathematics, Elsevier, 2013, 313 (8), pp.967-974. 〈http://www.sciencedirect.com/science/article/pii/S0012365X13000289〉. 〈10.1016/j.disc.2013.01.011〉. 〈hal-00821609〉

### Métriques

Consultations de la notice

## 356

Téléchargements de fichiers