Subdivisions of oriented cycles in digraphs with large chromatic number - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

Subdivisions of oriented cycles in digraphs with large chromatic number

Subidvisions de cycles orientés dans les graphes dirigés de fort nombre chromatique

Résumé

An {\it oriented cycle} is an orientation of a undirected cycle. We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).
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$).
Fichier principal
Vignette du fichier
RR-8865.pdf (597.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01277578 , version 1 (23-02-2016)

Identifiants

  • HAL Id : hal-01277578 , version 1

Citer

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⟩
226 Consultations
196 Téléchargements

Partager

Gmail Facebook X LinkedIn More