# Easy instances of the coloring problem on graphs with degree at most 4

Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.

In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?

For example: We know that graphs with bounded degree $$d$$ can be greedily colored with $$d+1$$ colors. But that by itself isn't optimal, since there are graphs in that class that can be colored with even fewer colors.
One way to fix that is by only considering the subclass of bounded-degree graphs that also need at least $$d+1$$ colors, ensuring that the greedy coloring is also the optimal one. So for example, the subclass of graphs of degree 4 that contain a 5-clique.