Skip to Main content Skip to Navigation

Oriented trees in digraphs.

Louigi Addario-Berry 1 Frédéric Havet 2 Claudia Linhares Sales 3 Bruce Reed Stéphan Thomassé 4 
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Sunday, January 2, 2011 - 7:13:53 PM
Last modification on : Saturday, June 25, 2022 - 11:05:39 PM
Long-term archiving on: : Monday, November 5, 2012 - 3:05:56 PM


Files produced by the author(s)


  • HAL Id : inria-00551133, version 1


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⟩



Record views


Files downloads