Coloring Graphs With Forbidden Almost Bipartite Subgraphs

ABSTRACT Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph , there exists a quantity such that whenever is an ‐free graph of maximum degree . The largest class of connected graphs 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 for some ). However, the optimal value for remains unknown even for such graphs. Bollobás showed, using random regular graphs, that when contains a cycle. On the other hand, Davies, Kang, Pirot, and Sereni recently established an upper bound of . We improve this to a uniform constant, showing for every almost bipartite graph . This surprisingly makes the bound independent of in all the known cases of the conjecture. 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.