Bispindles in strongly connected digraphs with large chromatic number

Nathann Cohen 1 Frédéric Havet 2 William Lochet 2, 3 Raul Lopes 4
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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
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).
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01810706
Contributor : Frederic Havet <>
Submitted on : Friday, June 8, 2018 - 10:23:26 AM
Last modification on : Thursday, February 7, 2019 - 4:56:59 PM
Document(s) archivé(s) le : Sunday, September 9, 2018 - 4:06:13 PM

File

6922-24594-2-PB.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

314

Files downloads

40