We will prove that the problem of distinguishing between 3-colorable and not even 4-colorable graphs is NP-hard. It is an immediate corollary of a more general result. For a fixed graph H, the H-coloring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami conjectured that hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colorable and those that are not H-colorable. We will prove this conjecture in the cases when both G and H are 4-colorable. This is a joint work with Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner.