Bispindle in strongly connected digraphs with large chromatic number

Abstract : A (k 1 + k 2)-bispindle is the union of k 1 (x, y)-dipaths and k 2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-bispindle B, there exists an integer k such that every strongly connected digraph with chromatic number greater than k contains a subdivision of B. We investigate generalisations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any (3 + 0)-bispindle or (2+2)-bispindle. Then we show that for any k, there exists γ k such that every strongly connected digraph with chromatic number greater than γ k contains a (2 + 1)-bispindle with the (y, x)-dipath and one of the (x, y)-dipaths of length at least k.
Type de document :
Article dans une revue
Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.69 - 74. 〈10.1016/j.endm.2017.10.013〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01634307
Contributeur : Frederic Havet <>
Soumis le : lundi 13 novembre 2017 - 22:47:45
Dernière modification le : jeudi 16 novembre 2017 - 01:09:41

Fichier

template.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nathann Cohen, Frédéric Havet, William Lochet, Raul Lopes. Bispindle in strongly connected digraphs with large chromatic number. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.69 - 74. 〈10.1016/j.endm.2017.10.013〉. 〈hal-01634307〉

Partager

Métriques

Consultations de la notice

19

Téléchargements de fichiers

3