Characterisation of graphs that are not 3-colorable
As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs.

However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem states every triangle-free planar graph is 3-colorable. Furthermore, such graphs can be 3-colored in linear time. In a random graph setting, almost all graphs with $2.522n$ edges are not 3-colorable [1].

You can find plenty of graph classes for which 3-coloring is easy on ISGCI.



[1] Achlioptas, D., &amp; Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3-colorable. Electronic Journal of Combinatorics, 6(1), R29.