A cycle with two blocks c(k,l) is an oriented cycle consisting of two internally disjoint directed paths of lengths at least k and l, respectively, from a vertex to another one. In 2007, Addario-Berry, Havet, and Thomassé asked if every strongly connected digraph D containing no c(k,l) has chromatic number at most k+l−1. In this talk, I show that such a digraph D has chromatic number at most O((k+l)²), improving the previous upper bound O((k+l)⁴) of Cohen, Havet, Lochet, and Nisse.

This is joint work with Seog-Jin Kim, Jie Ma, and Boram Park.