Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph. More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, for $k\ge 3$.
- J Bulín, A Krokhin, J Opršal. Algebraic Approach to Promise Constraint Satisfaction, STOC 2019. doi:10.1145/3313276.3316300 (preprint)
Turning the question around:
Is deciding if a 5-colourable graph is 3-colourable NP-hard?