Back to Search Start Over

Bispindles in strongly connected digraphs with large chromatic number

Authors :
Raul Lopes
Nathann Cohen
Frédéric Havet
William Lochet
Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI)
Laboratoire de Recherche en Informatique (LRI)
CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Combinatorics, Optimization and Algorithms for Telecommunications (COATI)
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 (... - 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)
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)-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)
Modèles de calcul, Complexité, Combinatoire (MC2)
Laboratoire de l'Informatique du Parallélisme (LIP)
École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Parallelism, Graphs and Optimization Research Group (ParGO)
Universidade Federal do Ceará = Federal University of Ceará (UFC)
Laboratoire de Recherche en Informatique ( LRI )
Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -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 ( COMRED )
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S )
Université Nice Sophia Antipolis ( UNS )
Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Nice Sophia Antipolis ( UNS )
Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S )
Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS )
Parallelism, Graphs and Optimization Research Group ( ParGO )
Universidade Federal do Ceará ( UFC )
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)
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)
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)
École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Source :
The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Open Journal Systems, 2018, Scopus-Elsevier, Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2018, The Electronic Journal of Combinatorics, 2018, ⟨10.37236/6922⟩
Publication Year :
2018
Publisher :
HAL CCSD, 2018.

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 $(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(k_1,k_2;k_3)$ denote the $(2,1)$-bispindle formed by three internally disjoint dipaths between two vertices $x,y$, two $(x,y)$-dipaths, one of length $k_1$ and the other of length $k_2$, and one $(y,x)$-dipath of length $k_3$. We conjecture that for any positive integers $k_1, k_2,k_3$, there is an integer $g(k_1,k_2,k_3)$ such that every strongly connected digraph with chromatic number greater than $g(k_1,k_2,k_3)$ contains a subdivision of $B(k_1,k_2;k_3)$. As evidence, we prove this conjecture for $k_2=1$ (and $k_1, k_3$ arbitrary).

Details

Language :
English
ISSN :
10778926
Database :
OpenAIRE
Journal :
The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Open Journal Systems, 2018, Scopus-Elsevier, Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2018, The Electronic Journal of Combinatorics, 2018, ⟨10.37236/6922⟩
Accession number :
edsair.doi.dedup.....8202758fc6ef6463bdc3b1bb9a4c9713
Full Text :
https://doi.org/10.37236/6922⟩