  Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite
graph $F$, there exists a quantity $c(F)$ such that $\chi(G) \leqslant (c(F) +
o(1)) \Delta / \log\Delta$ whenever $G$ is an $F$-free graph of maximum degree
$\Delta$. The largest class of connected graphs $F$ for which this conjecture
has been verified so far, by Alon, Krivelevich, and Sudakov themselves,
comprises the almost bipartite graphs (i.e., subgraphs of the complete
tripartite graph $K_{1,t,t}$ for some $t \in \mathbb{N}$). However, the optimal
value for $c(F)$ remains unknown even for such graphs. Bollob\'{a}s showed,
using random regular graphs, that $c(F) \geqslant 1/2$ when $F$ contains a
cycle. On the other hand, Davies, Kang, Pirot, and Sereni recently established
an upper bound of $c(K_{1,t,t}) \leqslant t$. We improve this to a constant,
showing $c(F) \leqslant 4$ for every almost bipartite graph $F$. This
surprisingly makes the bound independent of $F$ in all the known cases of the
conjecture, leading us to make a new conjecture that $c(F)$ is always bounded
above by some constant $c$ independent of $F$. We also establish a more general
version of our bound in the setting of DP-coloring (also known as
correspondence coloring) and consider some algorithmic consequences of our
results.
