Bispindles in strongly connected digraphs with large chromatic number

Nathann Cohen 1 Frédéric Havet 2 William Lochet 2 Raul Lopes 3
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
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
Abstract : A (k1 + k2)-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (1, 1)- 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 generalizations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any (3,0)- bispindle or (2,2)-bispindle. We then consider (2,1)-bispindles. Let B(k1,k2;k3) denote the (2, 1)-bispindle formed by three internally disjoint dipaths between two vertices x, y, two (x, y)-dipaths, one of length k1 and the other of length k2, and one (y,x)-dipath of length k3. We conjecture that for any positive integers k1,k2,k3, there is an integer g(k1,k2,k3) such that every strongly connected digraph with chromatic number greater than g(k1, k2, k3) contains a subdivision of B(k1, k2; k3). As evidence, we prove this conjecture for k2 = 1 (and k1, k3 arbitrary).
Type de document :
Article dans une revue
The Electronic Journal of Combinatorics, Open Journal Systems, 2018
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01810706
Contributeur : Frederic Havet <>
Soumis le : vendredi 8 juin 2018 - 10:23:26
Dernière modification le : mercredi 17 octobre 2018 - 17:08:02
Document(s) archivé(s) le : dimanche 9 septembre 2018 - 16:06:13

Fichier

6922-24594-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01810706, version 1

Citation

Nathann Cohen, Frédéric Havet, William Lochet, Raul Lopes. Bispindles in strongly connected digraphs with large chromatic number. The Electronic Journal of Combinatorics, Open Journal Systems, 2018. 〈hal-01810706〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

31