Subdivisions of two blocks cycles in digraphs with large chromatic number

par Darine Al Mniny (Université Claude Bernard Lyon 1)

mardi 25 sept. 2018, 10:45 → 11:45 Europe/Paris

Bât. Braconnier, salle Fokko du Cloux (ICJ, Université Lyon 1)

Let k and l be positive integers with k >=l . A cycle with two blocks C(k,l) is an oriented cycle formed by the union of two internally disjoint directed paths of lengths k and l respectively. Recently, Kim et al. proved that any strong digraph containing no subdivisions of C(k,l) has chromatic number at most 12k^2. In fact, we are able to improve this upper bound to 4k^2, not only for strong digraphs  but also for digraphs having a spanning out-tree.  Moreover, we prove that every digraph containing a Hamiltonian directed path with no subdivisions of C(k,l) has chromatic number at most 3(k-1).