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 metadatas

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

1056

Files downloads

143