Skip to Main content Skip to Navigation
Journal articles

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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634307
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Monday, November 13, 2017 - 10:47:45 PM
Last modification on : Wednesday, October 27, 2021 - 4:45:20 AM
Long-term archiving on: : 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

1431

Files downloads

965