Bispindles in strongly connected digraphs with large chromatic number
type: Item
instance of: scholarly article
title: Bispindles in strongly connected digraphs with large chromatic number
zbMATH Open document ID: 1388.05077
author: Nathann Cohen
author: Frédéric Havet
author: William Lochet
author: Raul Lopes
published in: The Electronic Journal of Combinatorics
publication date: 2018-06-14T00:00:00Z
full work available at URL: v25i2p39
review text: Summary: 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).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6888448
zbMATH Keywords: digraph
zbMATH Keywords: chromatic number
zbMATH Keywords: subdivisions
MaRDI profile type: Publication
cites work: Paths with two blocks in \(n\)-chromatic digraphs
cites work: Oriented trees in digraphs
cites work: Subdivisions in digraphs of large out-degree or large dichromatic number
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: Q5422499
cites work: Q3900086
cites work: Antidirected Subtrees of Directed Graphs
cites work: Subdivisions of oriented cycles in digraphs with large chromatic number
cites work: Graph Theory and Probability
cites work: Q5545303
cites work: Zur algebraischen Begründung der Graphentheorie. I
cites work: Cycles with two blocks in k‐chromatic digraphs
cites work: Nombre chromatique et plus longs chemins d'un graphe
cites work: Q5331780
description: scientific article; zbMATH DE number 6888448