Coloring graphs with forbidden almost bipartite subgraphs

James Anderson, Anton Bernshteyn, Abhishek Dhawan

Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph $F$, there exists a quantity $c(F)$ such that $\chi (G)\le (c(F)+o(1))\Delta /\log \Delta$ whenever $G$ is an $…