Bispindle in strongly connected digraphs with large chromatic number

Nathann Cohen (1) , Frédéric Havet (2) , William Lochet (3) , Raul Lopes (4)

1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
3 CRISAM - Inria Sophia Antipolis - Méditerranée
4 ParGO - Parallelism, Graphs and Optimization Research Group

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 (2 + 0)-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 for any k, there exists γ k such that every strongly connected digraph with chromatic number greater than γ k contains a (2 + 1)-bispindle with the (y, x)-dipath and one of the (x, y)-dipaths of length at least k.

Mots clés: chromatic number; Digraph; subdivision

Domaines: Mathématique discrète [cs.DM]

Nathann Cohen, Frédéric Havet, William Lochet, Raul Lopes. Bispindle in strongly connected digraphs with large chromatic number. Electronic Notes in Discrete Mathematics, 2017, 62, pp.69 - 74. ⟨10.1016/j.endm.2017.10.013⟩. ⟨hal-01634307⟩