Back to Search Start Over

Bispindles in strongly connected digraphs with large chromatic number

Authors :
Cohenn, N.
Havet, F.
Lochet, W.
Lopes, R.
Publication Year :
2017

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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1703.02230
Document Type :
Working Paper