One of the most successful approaches towards design of efficient algorithms for graph coloring (in restricted graph classes) is through study of structural properties of critical graphs, i.e., minimal obstructions for given chromatic number. The talk will give overview of known structural properties and corresponding algorithms, focusing especially on recent results following from the hyperbolicity theory, applications of the potential method, and computer-assisted enumeration.