Colouring graphs with prescribed induced cycle lengths

In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is ${\displaystyle ^I(4,5)}$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of ${\displaystyle ^I(4,5)}$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every ${\displaystyle G{\in }^I(n₁,n₂)}$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class ${\displaystyle ^I(n₁,n₂)}$. Here we obtain the surprising result that there exists no linear χ-binding function for ${\displaystyle ^I(3,4)}$.