Bispindles in strongly connected digraphs with large chromatic number

Description

A (k1 + k2)-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 (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(k1,k2;k3) denote the (2, 1)-bispindle formed by three internally disjoint dipaths between two vertices x, y, two (x, y)-dipaths, one of length k1 and the other of length k2, and one (y,x)-dipath of length k3. We conjecture that for any positive integers k1,k2,k3, there is an integer g(k1,k2,k3) such that every strongly connected digraph with chromatic number greater than g(k1, k2, k3) contains a subdivision of B(k1, k2; k3). As evidence, we prove this conjecture for k2 = 1 (and k1, k3 arbitrary).

Abstract

International audience

Additional details