Bispindle in strongly connected digraphs with large chromatic number

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

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Bispindle in strongly connected digraphs with large chromatic number