Bispindles in strongly connected digraphs with large chromatic number

Nathann Cohen¹ ; Frédéric Havet² ; William Lochet³ ; Raul Lopes⁴

¹CNRS, LRI, Univ. Paris Sud, Orsay, France
²Université Cote d'Azur, I3S, INRIA
³Université Cote d'Azur, I3S, INRIA LIP, ENS Lyon
⁴Departamento de Computaçao, Universidade Federal do Ceará, Fortaleza, Brazil

The electronic journal of combinatorics, Tome 25 (2018) no. 2

Résumé

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,x)$-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).

Détail

DOI : 10.37236/6922

Classification : 05C20, 05C15, 05C40
Mots-clés : digraph, chromatic number, subdivisions