Bispindles in strongly connected digraphs with large chromatic number

作者：Cohen Nathann; Havet Frederic; Lochet William^*; Lopes Raul

来源：Electronic Journal of Combinatorics, 2018, 25(2): P2.39.

DOI：10.37236/6922

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

• 出版日期2018-6-8
• 单位INRIA