Bispindles in Strongly Connected Digraphs with Large Chromatic Number

Source 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).