Colouring graphs with forbidden bipartite subgraphs

A conjecture of Alon, Krivelevich and Sudakov states that, for any graph F, there is a constant c(F) > 0 such that if G is an F-free graph of maximum degree Delta, then chi(G) <= c(F) Delta/ log Delta. Alon, Krivelevich and Sudakov verified this conjecture for a class of graphs F that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot and Sereni that if G is Kt,t-free, then chi(G) <= (t + o(1)) Delta / log Delta as Delta -> infinity. We improve this bound to (1 + o(1)) Delta / log Delta, making the constant factor independent of t. We further extend our result to the DP-colouring setting (also known as correspondence colouring), introduced by Dvo.rak and Postle.