Easy instances of the coloring problem on graphs with degree at most 4
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".

But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.