Bispindles in strongly connected digraphs with large chromatic number (Q1640212)

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