Back to Search
Start Over
Bispindle in strongly connected digraphs with large chromatic number
- 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.
- Subjects :
- Strongly connected component
business.industry
Applied Mathematics
Digraph
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
Disjoint sets
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Combinatorics
Integer
010201 computation theory & mathematics
chromatic number
subdivision
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
Chromatic scale
business
Mathematics
Subdivision
Subjects
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⟩