pith. sign in

arxiv: 1703.02230 · v1 · pith:DLFALZNUnew · submitted 2017-03-07 · 🧮 math.CO

Bispindles in strongly connected digraphs with large chromatic number

classification 🧮 math.CO
keywords bispindlechromaticconnecteddipathsnumberstronglydigraphslarge
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.