Finding a class of graphs for which vertex coloring is NP-hard
This PDF defines a graph for which solving a 3-SAT formula is equivalent to determining if the graph is 3-colorable. Finding the vertex coloring of these graphs would solve the 3-SAT problem, so the vertex coloring problem on these graphs is at least as hard as an NP-complete problem. Therefore, solving the vertex coloring problem on these graphs is NP-hard.