Back to Search
Start Over
Bispindles in strongly connected digraphs with large chromatic number
- 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).
- Subjects :
- Discrete mathematics
Strongly connected component
Conjecture
Applied Mathematics
[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]
Disjoint sets
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
Integer
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Geometry and Topology
Chromatic scale
Combinatorics (math.CO)
Mathematics
Subjects
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⟩