NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. - Yahli Hecht; Dor Minzer; Muli Safra (APPROX/RANDOM, 2023)