Independent sets and colorings of $K_{t,t,t}$-free graphs

Ajtai, Erdős, Komlós, and Szemerédi conjectured in 1981 that for every graph $F$, every $n$-vertex $F$-free graph of average degree $d$ contains an independent set of size $Ω(n \log d / d)$. The largest class of graphs for which this was previously known was established by Alon, Krivelevich, and Sudakov in 1999, who proved it for the so-called almost bipartite graphs, namely subgraphs of $K_{1,t,t}$. We prove the conjecture for all 3-colorable graphs $F$, i.e., subgraphs of $K_{t,t,t}$, representing the first progress on the problem in more than 25 years. More precisely, we show that every $n$-vertex $K_{t,t,t}$-free graph of average degree $d$ contains an independent set of size at least $(1 - o(1)) n \log d / d$, matching Shearer's celebrated bound for triangle-free graphs (the case $t = 1$) and thereby yielding a substantial strengthening of it. Our proof combines a new variant of the Rödl nibble method for constructing independent sets with a Turán-type result on $K_{t,t,t}$-free graphs. A closely related conjecture of Alon, Krivelevich, and Sudakov (1999) asserts that any $F$-free graph of maximum degree at most $Δ$ has chromatic number $O(Δ/ \log Δ)$. This was previously known only for almost bipartite graphs (verified by Alon, Krivelevich, and Sudakov themselves), while most recent results were concerned with improving the leading constant factor in the case where $F$ is almost bipartite. We also establish this conjecture for all $3$-colorable graphs $F$, representing the first progress toward the conjecture since it was posed.