Bispindle in strongly connected digraphs with large chromatic number

Nathann Cohen 1 Frédéric Havet 2 William Lochet 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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634307
Contributor : Frederic Havet <>
Submitted on : Monday, November 13, 2017 - 10:47:45 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Wednesday, February 14, 2018 - 4:02:49 PM

File

template.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

715

Files downloads

55