Bispindles in strongly connected digraphs with large chromatic number

2017/03/07 by Cohenn, N., Havet, F., Lochet, W. +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1703.02230

Abstract

A (k₁+k₂)-bispindle is the union of k₁ (x,y)-dipaths and k₂ (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 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 strongly connected digraphs with large chromatic number contains a (2,1)-bispindle, where at least one of the (x,y)-dipaths and the (y,x)-dipath are long.

Related

• Remarks on the subdivisions of bispindles and two-blocks cycles in highly chromatic digraphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Cycles with two blocks in k-chromatic digraphs
• Subdivisions in dicritical digraphs with large order or digirth
• (Δ-1)-dicolouring of digraphs