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

Question

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?

Answer 1

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.

Answer 2

As the other answer states, any class that is already easy to color can obviously be additionally restricted to bounded-degree graphs. But if you are looking for restrictions that only yield easily colored graphs in combination with the bounded-degree restriction, that also works.

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.

(Edit: There's also something called Brooks' theorem, which says that unless the graph really does contain such a 5-clique, it will actually be 4-colorable. But I can't see if it also says that this coloring can be found in polynomial time.)