Back to Search Start Over

Bispindle in strongly connected digraphs with large chromatic number

Authors :
Raul Lopes
William Lochet
Frédéric Havet
Nathann Cohen
Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI)
Laboratoire de Recherche en Informatique (LRI)
Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Combinatorics, Optimization and Algorithms for Telecommunications (COATI)
Inria Sophia Antipolis - Méditerranée (CRISAM)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED)
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Institut National de Recherche en Informatique et en Automatique (Inria)
Parallelism, Graphs and Optimization Research Group (ParGO)
Universidade Federal do Ceará = Federal University of Ceará (UFC)
ANR-13-BS02-0007,Stint,Structures Interdites(2013)
Université Nice Sophia Antipolis (... - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Source :
Electronic Notes in Discrete Mathematics, Electronic Notes in Discrete Mathematics, 2017, 62, pp.69-74. ⟨10.1016/j.endm.2017.10.013⟩, Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.69-74. ⟨10.1016/j.endm.2017.10.013⟩
Publication Year :
2017
Publisher :
HAL CCSD, 2017.

Abstract

A ( k 1 + k 2 )-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 (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.

Details

Language :
English
ISSN :
15710653
Database :
OpenAIRE
Journal :
Electronic Notes in Discrete Mathematics, Electronic Notes in Discrete Mathematics, 2017, 62, pp.69-74. ⟨10.1016/j.endm.2017.10.013⟩, Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.69-74. ⟨10.1016/j.endm.2017.10.013⟩
Accession number :
edsair.doi.dedup.....494f049c749ab8928932cedcb47edeec
Full Text :
https://doi.org/10.1016/j.endm.2017.10.013⟩