Oriented trees in digraphs.

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.
Type de document :
Rapport
[Research Report] RR-7502, INRIA. 2011
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00551133
Contributeur : Frederic Havet <>
Soumis le : dimanche 2 janvier 2011 - 19:13:53
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : lundi 5 novembre 2012 - 15:05:56

Fichier

RR-7502.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00551133, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

565

Téléchargements de fichiers

342