Subdivisions of oriented cycles in digraphs with large chromatic number

Nathann Cohen 1 Frédéric Havet 2 William Lochet 2, 3 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Un {\it cycle orienté} est l'orientation d'un cycle. Nous prouvons que pour tout cycle orienté $C$ il existe des graphes dirigés sans subdivisions de $C$ (en tant que sous graphe) et de nombre chromatique arbitrairement grand. Par ailleurs, nous prouvons que pour tout cycle a deux bloques, tout graphe dirigé fortement connexe de nombre chromatique suffisamment grand contient une subdivision de $C$. Nous prouvons aussi un resultat semblable sur le cycle antidirigé de taille quatre (avec deux sommets de degré sortant $2$ et deux sommets de degré entrant $2$).
Type de document :
Rapport
[Research Report] RR-8865, LRI - CNRS, University Paris-Sud; LIP - ENS Lyon; INRIA Sophia Antipolis - I3S. 2016, pp.25
Liste complète des métadonnées

https://hal.inria.fr/hal-01277578
Contributeur : William Lochet <>
Soumis le : mardi 23 février 2016 - 15:42:13
Dernière modification le : samedi 18 février 2017 - 01:20:41
Document(s) archivé(s) le : mardi 24 mai 2016 - 11:18:00

Fichiers

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

Identifiants

  • HAL Id : hal-01277578, version 1

Citation

Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse. Subdivisions of oriented cycles in digraphs with large chromatic number. [Research Report] RR-8865, LRI - CNRS, University Paris-Sud; LIP - ENS Lyon; INRIA Sophia Antipolis - I3S. 2016, pp.25. <hal-01277578>

Partager

Métriques

Consultations de
la notice

194

Téléchargements du document

75